IZKP protocol executed sequentially

IP executed in parallel

The first protocol can be proved ZK, but the second is not believed to be so? What quality of the parallelization makes it such that an identical protocol executed in parallel, as opposed to sequentially, would remove its ZK properties?

EDIT#1: The source of the IP's was asked for so I shall say, they are from some course notes of a graduate cryptography course at UCLA, from a few years ago, and given to be based off of the book "Foundations of Crypto" by Goldreich.

  • 1
    $\begingroup$ Please do your homework; this topic is discussed in many sources. Have you actually read some? What did you not understand? $\endgroup$ – fkraiem Dec 21 '17 at 1:51
  • $\begingroup$ @fkraiem I mean no disrespect, but you seem to like to comment on my posts with pejorative information, and then vanish without being helpful at all. I would not have asked the question if I honestly thought that it had been answered by a previous one. Please, in the future instead of being so obviously biting and sarcastic, add something of value, like a link to a question you believe to be similar. If indeed you are correct then your comment would be many characters fewer and this question would've closed. If you can't say anything productive and nice you need not say anything at all. $\endgroup$ – z.karl Dec 21 '17 at 2:46
  • 2
    $\begingroup$ Can you please put down the source for the question? $\endgroup$ – mikeazo Dec 21 '17 at 12:10

Hint: look at the security proof of the zero-knowledge property of the first scheme. I recommend writing it fully and formally, if you want the solution to become clear. It relies on a common "rewinding" strategy, and requires in particular to guess in advance the challenge of the verifier, with non-negligible probability. Now, what happens to this strategy when we consider parallel repetitions instead? Can you see where exactly it breaks down? We can give you further hints if you explain exactly what you tried and tell us where you are stuck afterward.

| improve this answer | |
  • $\begingroup$ In an attempt of the formal Simulator for the 1st scheme I do 2 main things [1] record a rndm tape for the dishonest verifier V [2] run a loop k times in which I (A) record the state and configuration of V (B) run a loop in which I pick a rndm bit b' and run the first scheme's protocol with G_b' in place of G_0 in the first step, exiting only if V accepts else rewinding V and picking another rndm b'. What I don't understand is if I replace the k-loop with k threads, some threads will take longer than others, but I see no reason for knowledge to be lost by running scheme 1 side-by-side k times. $\endgroup$ – z.karl Dec 28 '17 at 3:07
  • $\begingroup$ When running the parallel simulation, you do not rewind many independent copies of P in parallel: the verifier expects to receive all parallel queries "at once" in a single flow, so you must hand him all of them. It does not run in "separate threads". But now, if you pick all the possible random b' for the k parallel flows, the probability that you correctly guessed all queries of V becomes negligible. So you must restart all simultaneous flows until you make a "global correct guess", which takes time exponential in k. $\endgroup$ – Geoffroy Couteau Dec 28 '17 at 8:05
  • $\begingroup$ That makes perfect sense, because S would have to guess k possible bits independently giving him a 1/2^k probability of success which is negligible. However, why is the "separate threads" (st) analogy incorrect in this parallel case. Isn't this the natural analogy to any parallel protocol? You also mention that V must receive all queries at once, I do not see how this is precluded in the "st" analogy. Why not just treat it the same as defending against a timing attack where if thread A is faster than thread B we make thread A and B output at the same time, after they're both finished? $\endgroup$ – z.karl Jan 1 '18 at 23:30
  • 1
    $\begingroup$ Unfortunately, comments are not appropriate for extended discussion, if you want me to help you with working out the details of these proofs, we can discuss by mail :) $\endgroup$ – Geoffroy Couteau Jan 1 '18 at 23:55

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.