1
$\begingroup$

I'm trying as autodidact to read chapter 4 of Foundation of Cryptography by Oded Goldreich (just to let you "tune" your answers, I have engineering background).

If I'm correctly understanding, giving a perfect simulator $S_1$ the possibility to halt is not a problem because we can define a simulator $S_2$ which repeats $S_1$ let's say $n$ times, outputting the result of the first not-halting $S_1$ iteration, or a "dummy" result if ALL $S_1$ iterations halt. This way the probability of $S_2$ outputting the dummy result can be lowered as liked with the growth of $n$.

$S_1$ halting probability is bounded above by $1/2$, but why? It seems to me that every $S_1$ halting probability $<1$ will be lowered towards $0$ by a sufficient large $n$. More, the simulator one seems a very different argument from completeness/soundness probabilities, where the strict $1/2$ threshold is justified by the majority rule applied to that (different) repetitions strategy.

And, btw, is there any reason to choose $S_1$ repetitions value $n$ to be the same as the other repetitions number needed to pass from weak completeness/soundness to stronger ones? Or are the numbers of the two kinds of iterations mutually independent? I guess this doubt comes from me being confused about if $S_2$ is the simulator for the weak IP, or for the stronger IP...

Thanks!

$\endgroup$
4
  • $\begingroup$ you are right, there is nothing specific about 1/2: any constant bounded away from 1 would do the trick. $\endgroup$ Aug 27, 2021 at 17:43
  • $\begingroup$ and no, nothing forces the two $n$'s to be the same, they are two different quantities. The point each time is always "we can make the probability of breaking soundness / the probability to failing to extract exponentially small", but repetitions of the interactive proof versus repeated use of the simulator are different things. $\endgroup$ Aug 27, 2021 at 17:47
  • $\begingroup$ Thanks @GeoffroyCouteau ! So I wonder why <=1/2 is used: maybe because -being the halting possibility a way to weaken a "real" perfect simulator to make it applicable- we want to keep halts occurences as lower as possibile than 1, and 1/2 is the lower threshold permitting ZK for both Graph Isomorphism and G3C? Any opinion about it? $\endgroup$
    – baro77
    Aug 28, 2021 at 10:13
  • $\begingroup$ I really think it's arbitrary. The reason is probably something as simple as: n invocations of the simulator give a probability 1/2^n of failure, and we're used to estimate "small" in terms of 2^(-something) $\endgroup$ Aug 28, 2021 at 11:46

0

Your Answer

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

Browse other questions tagged or ask your own question.