Maybe a silly question, but regarding supplying the same distribution when proving zero knowledge:

In question 4 of HW5 the protocol chooses a random r, then V flips a coin for b and a is decided based on that coin.

Does this not mean that any triplet (r,b,a) is distributed the same way as in the original protocol so long as we take some random r, flip a coin for b and then return a = b?

Whats the catch?

Note that a is not the bit that V chooses. a is a number in $\mathbb{Z}_n^*$

To simulate the view you have to send a number that is distributed the same as in the scheme. The catch is that since the simulator does not know x, it can't do exactly what P does.

Yeah, but a is distributed like a coin toss, if b = 0 it's one thing, otherwise it's the other.

Or are you saying that a's distribution depends on that of x (in the case of b = 1) and therefore knowing b is not enough to choose an a that distributes like it does in the protocol itself?

I commented on the fact that you wrote to set a=b.

If b=0, then yes, it is just a random coin toss.

If b=1, then, not quite, since, at a minimum, it must pass the verifier's test of $a^2=zy$. Knowing b is enough but explaining how would be answering the question.

But why must it pass the test?

What's confusing me is just how far "identical distribution" goes.

If I do set a = b (or something else that distributes correctly) then sure, it wont pass the verifiers test, but it would still distribute half and half like it does in the protocol.

Is distribution being the same really enough? Or do we need a transcript which is indistinguishable from a proper run? I dont think the two are the same.

Intuitively, for the views to be indistinguishable, there should be no way to tell them apart (there are 3 relevant kinds of indistinguishability (that I know of) but Ill ignore that here).

if a doesnt pass the test when b=1, then we can use that test to tell apart the two distributions- in the real case the test always passes, and in what you proposed it will fail (up to negligible probability).

I agree that seeing a alone, it would look random. But its note quite random in the context of the whole conversation…