Funções unidirecionais com relação a vários limites de recursos

13

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 ( )?NTIME (n)

Eu estou bem com a pior dureza de invertibilidade em relação aos limites de recursos acima.

Mohammad Al-Turkistany
fonte
Você já viu eprint.iacr.org/2013/001.pdf ? O tópico deste artigo pode ou não ser exatamente relevante para você, mas as técnicas do artigo (ou talvez até as citações) podem levar a algo útil.
Daniel Apon
O resumo não ajuda, mas obrigado pela sua ajuda.
Mohammad Al-Turkistany
Oh, bem - espero que a nova resposta o faça. :)
Daniel Apon
Sim, Ele faz :)
Mohammad Al-Turkistany

Respostas:

11

0 0

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(uma1,...,uman,S): =(uma1,...,uman,EuSumaEumod2n)

Manu
fonte
Obrigado Emanuele. Isso responde ao caso do espaço de log. Apenas para completar, você poderia listar algumas dessas funções em sua resposta.
Mohammad Al-Turkistany
Eu adicionei dois exemplos.
Manu
Muito obrigado Emanuele. Existe um insight que explique a dureza de inverter essas funções (pelos algoritmos LOGSPACE)?
Mohammad Al-Turkistany