# ZK: Repetitions to lower simulator halt probability

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!

• you are right, there is nothing specific about 1/2: any constant bounded away from 1 would do the trick. Aug 27, 2021 at 17:43
• 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. Aug 27, 2021 at 17:47
• 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? Aug 28, 2021 at 10:13
• 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) Aug 28, 2021 at 11:46