ZK: Repetitions to lower simulator halt probability

baro77

12/27/22, 5:18 PM

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!

0 + 4

zero-knowledge-proofs

Geoffroy Couteau

12/27/22, 5:43 PM

you are right, there is nothing specific about 1/2: any constant bounded away from 1 would do the trick.

Geoffroy Couteau

12/27/22, 5:47 PM

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.

baro77

12/28/22, 10:13 AM

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?

Geoffroy Couteau

12/28/22, 11:46 AM

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)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: ZK: Repetitions to lower simulator halt probability

TH: ZK: การทำซ้ำเพื่อลดความน่าจะเป็นของการหยุดจำลอง

RO: ZK: Repetări pentru a reduce probabilitatea de oprire a simulatorului

RU: ZK: Повторы для снижения вероятности остановки симулятора

VI: ZK: Các lần lặp lại để giảm xác suất dừng giả lập

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.