HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What will i obtain if i apply a xor-ing a one way function and it's input?

Submitted by: @import:stackexchange-cs··
0
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.

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.