patternMinor
What will i obtain if i apply a xor-ing a one way function and it's input?
Viewed 0 times
xorobtainwhatingapplywayfunctioninputonewill
Problem
I know that a one-way function is informally a function that it's easy to compute but hard to invert.
If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function?
My intuition is that it's but i not really sure.
If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function?
My intuition is that it's but i not really sure.
Solution
Let $h$ be any one-way function, and define $f(x) = 0^{|x|} h(x)$. Note that $f$ is also one-way: it is easy to compute, and if you can invert $f$ you can invert $h$ (so since $h$ is hard to invert, so is $f$). But $g(x) = xh(x)$ is easy to invert.
Context
StackExchange Computer Science Q#7160, answer score: 6
Revisions (0)
No revisions yet.