Informalmente, funções unidirecionais são definidas com relação aos algoritmos PTIME. Eles são computáveis em tempo polinomial, mas não invertíveis em tempo polinomial de caso médio. A existência de tais funções é um importante problema em aberto na ciência da computação teórica.
Estou interessado em funções unidirecionais (não necessariamente para aplicativos criptográficos) definidas com relação a diferentes limites de recursos. Esses limites de recursos podem ser LOGSPACE ou não-determinismo limitado.
Existe um problema candidato (natural) unidirecional em relação aos algoritmos LOGSPACE? Existe um problema candidato (natural) unidirecional em relação a algoritmos de tempo linear não determinísticos ( )?
Eu estou bem com a pior dureza de invertibilidade em relação aos limites de recursos acima.
fonte
Respostas:
Dois exemplos específicos incluem:
Multiplicação de número inteiro (existem algumas sutilezas para o OWF padrão, mas se você se importa apenas com o pior caso, isso é suficiente)
O candidato Impagliazzo-Naor com base na soma do subconjunto: .f( um1, . . . , umn, S) : = ( a1, . . . , umn, ∑i ∈ SumaEumod2n)
fonte