2
$\begingroup$

This question follows directly on from How do I explain zero knowledge proof to my 7 year old cousin?

Most of the simplistic answers there suggest that proof is obtained iteratively, slowly reducing the probability of Peggy simply randomly going through the cave. Or counting leaves over and over. The Wikipedia page suggests the Peggy should demonstrate her magic skills 20 times. Later on there is mention of repeating the proof 128 times. That's a bit of a statistical difference.

In a real world situation of proving something like the existence of a correct 256 bit AES key, how many times would the proving have to be attempted for certainty?

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ The residual odds of winning by chance after $n$ tries are $2^{-n}$, and the answer is all about what "certainty" means. If you want one chance in 4 million millions, the Answer is 42. $\endgroup$ – fgrieu♦ Mar 27 '18 at 6:10
  • 1
    $\begingroup$ @fgrieu I know that piece of maths. But what is actually done? Specifically for the 256 bit AES key, would you need 256 tests (bit by bit) or just 20 like the wiki article? $\endgroup$ – Paul Uszak Mar 27 '18 at 9:54
  • $\begingroup$ So there is an aspect in the question related to efficiency of zero-knowledge proofs involving many bits. Perhaps that could be clarified in the question itself, which otheriwise seems to be about level of certainty (that was my reading, and what Geoffroy Couteau address in his nice answer). $\endgroup$ – fgrieu♦ Mar 27 '18 at 10:30
  • $\begingroup$ If the question is simply "how many repetitions do we usually use in cryptography for zero-knowledge proofs", the answer is less convoluted than my answer below: by experience, it varies but 40 is the number I see most often when concrete numbers are reported (this is a standard statistical security parameter in zero-knowledge proofs, or cut-and-choose). Note that this is a number given in papers willing to report concrete numbers, where it makes sense to pick it "not too large" to optimize for efficiency - in more theoretical papers, this is less crucial and most people would just go for 128. $\endgroup$ – Geoffroy Couteau Mar 28 '18 at 7:16
3
$\begingroup$

There is obviously no definite answer to that. The general principle, however, is not at all a problem of cryptography: it is a question with a long history in probability and economics. It is referred to as Cournot's principle in this answer of Bjørn Kjos-Hanssen on cstheory.stackexchange.

As detailed by the document which I linked to, the question has long bothered people, especially when it comes to law. When can magistrates declare moral certainty? If there is a 99.99% chance that a guy is the killer, can we safely condemn him? The general consensus is what is known as Cournot's principle, which connects mathematical probabilities with the empirical "real world":

rare events simply don't happen

Or, as put by Kolmogorov: if $P(E)$ is very small and we make a single trial, we can be practically certain that $E$ will not happen.

Of course, none of this really "answers the question". In reality, finding out which probability you will associate to certainty is essentially a matter of three things:

  1. How many trials could a cheater have?
  2. How strong is the incentive to cheat?
  3. How disastrous would be the rare event?

If the attacker has a single trial, and a mistake would not be the end of the world, go for $1/{2^{20}}$ and you'll be fine. If your life depends on the outcome, or an attacker could repeat trials as often as he wants until he succeeds, you want to take a large margin, and you can go for $1/{2^{128}}$.

Note: items 1 and 3 in my list above are, in fact, closely related. Indeed, extremely rare events appear all the time: take a deck of cards, shuffle it, pick ten cards. What was the probability that you would get exactly those ten cards? It's obviously extremely low. Most things are just not so important, so the situation where an unlikely event happens is in fact very common, as there are virtually many "trials" of "unimportant events". This justifies restricting our attention, not to any event, but to "situations with potentially disastrous outcomes": there are very few such situations, hence we get less trials to get a disastrous event.

Note 2: if you want more "actual numbers" for which some famous guy randomly decided that they indicate that an event is unlikely, look at Borel's choice in page 17 of the same pdf I linked to before: he mentions $10^{-6}$ as "uncertainty on the human scale", $10^{-15}$ as "uncertainty on the terrestrial scale", and $10^{-50}$ as "uncertainty on the cosmic scale". Which is, again, an attempted answer at the following question: how many trials does a human / the earth / the universe gets at producing an event with an important outcome?

| improve this answer | |
$\endgroup$

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.