0
$\begingroup$

enter image description here

enter image description here

I am able to understand how G(x) id generated. But then what is the use of variable z. Also if the probability is >1/2 + e then the distinguisher wins! Then how is this still a OWF

$\endgroup$
0
$\begingroup$

This is an example of proof by contradiction. If you have ever seen a proof that the square root of 2 is irrational, that probably used a similar logical argument. Our goal is to prove that $\mathcal A$ does not exist, but we do that by assuming it does exist and then deducing that something goes wrong. The place to pay attention is bullet 4 where we assume $\mathcal A$ exists; mathematicians and computer scientists could make life easier at this point by adding "SPOILER ALERT: It doesn't!". The next three bullets proceed from this assumption and at the end of bullet 7 the wheels fall off because, as you realised, we have constructed a case where the distinguisher wins and because we know that $G$ is a PRG this cannot happen. We go back to bullet 4 and realise that we must have gone wrong by assuming the existence of $\mathcal A$. We conclude that no such $\mathcal A$ can exist.

The variable $z$ is meant to represent a response to a challenge from the adversary. After that the proof shows how you can distinguish the response if you can lay your hands on $\mathcal A$ (SPOILER ALERT: You can't).

$\endgroup$
2
  • $\begingroup$ Thanks that really helps! $\endgroup$ Mar 21 at 8:04
  • $\begingroup$ You are correct that the proof sketch formulates the argument as a proof by contradiction. This is very annoying, confusing and completely unnecessary. You can formulate it in a much nicer way as simply upper bounding the success probability of any ppt $\mathcal{A}$. In my opinion that's how it should be done. $\endgroup$
    – Maeher
    Mar 21 at 12:02

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.