Criptografía: si f (x) es una función unidireccional, ¿f ‘(x) se define como f (x) con algunos bits eliminados aún unidireccionales?

Answer 1

Sí, f ‘(x) continuará siendo unidireccional.

Para ver intuitivamente por qué, supongamos que f ‘(x) no es unidireccional. En este caso, puede construir un mecanismo eficiente para invertir f (x), lo que contradiría su unidireccionalidad. Tenga en cuenta que el inversor para f (x) que construya no siempre producirá una respuesta correcta; sin embargo, será correcto un porcentaje no despreciable de veces.

En particular, S () sea la función que elimina un bit de la salida de f (x), de modo que f ‘(x) se pueda definir como S (f (x)).

Ahora, suponga que se le dio un valor y que es igual a f (x), donde x se elige de acuerdo con cualquier distribución de probabilidad que haga que f (x) sea unidireccional. Si f ‘(x) no es unidireccional, entonces debe haber una función eficientemente computable I’ () tal que f ‘(I’ (S (y))) = y con probabilidad no despreciable (es decir, I ‘( ) encuentra el inverso de y debajo de f ‘() eficientemente).

Ahora, considere el inversor candidato I () para f () que funciona de la siguiente manera: I (y) = I ‘(S (y)). En otras palabras, elimine el bit de y y luego aplique el inversor para f ‘(). Yo () no siempre produciré la respuesta correcta. En particular, digamos que el bit 1 se eliminó de y, entonces I () podría producir una respuesta en la que se eliminó un 0. Sin embargo, I () aún producirá la respuesta correcta con una probabilidad no despreciable.

Puede escribir este argumento de manera más formal y agregar algunos pasos más, pero esto significa más para darle algo de intuición.