Funciones de un solo sentido

De Wikipedia, la enciclopedia libre

Las funciones de un solo sentido son funciones que tienen la propiedad de ser fáciles de calcular pero difíciles de invertir. Fácil de calcular se refiere a que un algortimo la puede computar en tiempo polinomial, en función del largo de la entrada. Difícil de invertir significa que no hay algoritmo probabilístico que en tiempo polinomial puede computar una preimagen de f(x) cuando x es escogido al azar. Algunas personas conjeturan que el logaritmo discreto y la inversión RSA son funciones de un solo sentido.

[editar] Importancia

Si las funciones de un solo sentido existen, entonces la criptografía de clave pública (public key cryptography) es posible. Su existencia implicaría que P no es NP.

[editar] Conjetura actual

Está asumido pero no probado que existen las funciones de un solo sentido.

[editar] Enlaces externos

• W.Diffie, M.E.Hellman
• IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654
• Online copy (HTML)