Que vais-je obtenir si je demande un XOR-ment une fonction à sens unique et l'entrée de ce?

Question

Je sais que fonction à sens unique est officieusement une fonction qu'il est facile de compute mais difficile à inverser.
Si f (x) est une fonction à sens unique la fonction $ g (x) = x \ oplus f (x) $ est une fonction à sens unique? Mon intuition est qu'il est mais je pas vraiment sûr.

Answer 1

Soit $ h $ soit une fonction à sens unique, et définir $ f (x) = 0 ^ {| x |} h (x) $. Notez que $ f $ est à sens unique: il est facile de calculer, et si vous pouvez inverser $ f $, vous pouvez inverser $ h $ (donc depuis $ h $ est difficile à inverser, est donc $ f $). Mais $ g (x) = xh (x) $ est facile à inverser.