2
$\begingroup$

I'm currently learning about one-way functions. I have a book with the following exercise (Sadly there is no solution in the book...)

Let $g\colon \{0,1\}^n \to \{0,1\}^n$ be a one way function. Prove that $f\colon \{0,1\}^{2n} \to \{0,1\}^n$ with $f(v,w) := g(v)⊕w$ is NOT a one way function.

I don't really get how I can solve this exercise... because if $w$ is, for example, $0^n$, it would be a simple reduction to show that it is in fact a one-way function, right?

How can I get an advantage $>\mathit{negligible}(n)$ ?

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Aug 24 '17 at 8:43
2
$\begingroup$

The attacker is given $y = f(v,w)$ and must find $v$ and $w$. The attacker can generate a random $v_0$ and calculate $g(v_0)$; then they can simply calculate $w_0=y⊕g(v_0)$ and then return $(v_0,w_0)$, for which $f(v_0,w_0)=y \implies \Pr[\mathit{Invert}=1]=1>\mathit{negl}(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.