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$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Commented Aug 24, 2017 at 8:43

1 Answer 1

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 and acknowledge you have read our privacy policy.

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