Funciones unidireccionales con respecto a varios límites de recursos

13

Informalmente, las funciones unidireccionales se definen con respecto a los algoritmos PTIME. Son computables en tiempo polinomial pero no invertibles en tiempo polinomial de caso promedio. La existencia de tales funciones es un importante problema abierto en la informática teórica.

Estoy interesado en funciones unidireccionales (no necesariamente para aplicaciones criptográficas) definidas con respecto a diferentes límites de recursos. Dichos límites de recursos podrían ser LOGSPACE o no determinismo limitado.

¿Existe un problema candidato (natural) que sea unidireccional con respecto a los algoritmos LOGSPACE? ¿Existe un problema candidato (natural) que sea unidireccional con respecto a los algoritmos de tiempo lineal no determinista ( )?NTIME (n)

Estoy bien con la peor dureza de invertiblidad con respecto a los límites de recursos anteriores.

Mohammad Al-Turkistany
fuente
¿Has visto eprint.iacr.org/2013/001.pdf ? El tema de este documento puede o no ser exactamente relevante para usted, pero las técnicas en el documento (o tal vez incluso las citas) pueden conducir a algo útil.
Daniel Apon
El resumen no ayuda pero gracias por su ayuda.
Mohammad Al-Turkistany
Oh, bueno, espero que la nueva respuesta sí. :)
Daniel Apon
Sí, lo hace :)
Mohammad Al-Turkistany

Respuestas:

11

0 0

Dos ejemplos específicos incluyen:

Multiplicación de enteros (hay algunas sutilezas para el OWF estándar, pero si solo te importa el peor de los casos, esto es suficiente)

F(un1,...,unnorte,S): =(un1,...,unnorte,yoSunyomodificación2norte)

Manu
fuente
Gracias Emanuele Esto responde al caso Logspace. Solo para completar, ¿podría enumerar algunas de esas funciones en su respuesta?
Mohammad Al-Turkistany
He añadido dos ejemplos.
Manu
Muchas gracias Emanuele. ¿Existe alguna idea que explique la dureza de invertir esas funciones (mediante algoritmos LOGSPACE)?
Mohammad Al-Turkistany