Intuitivamente, no tiene que ser una función unidireccional, y puede ser fuerte. Pero no tengo experiencia particular con las pruebas de función unidireccionales, y no estoy seguro de cómo probar este resultado en particular.
Para la intuición, dejemos que f (x) sea un cifrado de bloque con una clave fija, es decir, una permutación fea pero fácilmente invertible. Esta no es una función unidireccional. Pero g (x) = f (x) ^ x es la construcción hash de Davies-Meyer, que es probablemente una función unidireccional fuerte. Entonces g (x) es una función unidireccional pero f (x) no lo es.
Si desea que g (x) sea “estrictamente débil”, es decir, no fuerte, simplemente haga algo diferente dependiendo de si x es par o impar, por ejemplo, f (x) = 0 si x es par. Entonces g (x) no será fuerte.
- Cómo entender el concepto de que 'si p entonces q' es equivalente a 'no p o q' Eg; 'Si muero, entonces me voy' es equivalente a 'Vivo o me voy'
- Cómo hacer una forma generalizada a partir de un conjunto dado de expresiones (pasos / algoritmo de deseo)
- ¿Qué es la reducción del tiempo polinomial?
- ¿Cómo funciona una calculadora electrónica?
- ¿Qué significa una garantía teórica en el aprendizaje automático?
Del mismo modo, podría hacer que g (x) sea una permutación fea pero fácilmente invertible cuando x es par, y una función unidireccional fuerte si x es impar (no use la patológica anterior). Entonces g (x) sería débil, pero con suerte f (x) sería fuerte.
Esto no constituye una prueba, porque aunque sé que los cifrados de bloque se siguen de funciones unidireccionales, no estoy seguro de lo que puede probar sobre las construcciones de Davies-Meyer.
EDITAR: f () definitivamente puede ser una función no unidireccional. Sea h (x) una función unidireccional, y sea g (x) = h (x) << | x |. Entonces f (x) = h (x) || x revela x.
