2
$\begingroup$

There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier.

Take the Ali Baba cave as an example:

The prover has a 50% chance of guessing the side of the cave correctly. That's why the procedure has to be done multiple rounds for the probablility of the prover not knowing a secret becomes reasonably small.

In this example the probability of guessing something correctly is $2^{-n}$, where $n$ is the number of rounds.

My questions are:

  • Is there a rule of thumb for how small this probability has to be?
  • What's the value of this probability in today's ZK protocols?
$\endgroup$
  • 1
    $\begingroup$ By definition, the probability has to be negligible. I.e., upper bounded by a negligible function in the security parameter. $\endgroup$ – Maeher Dec 7 '18 at 14:09
5
$\begingroup$

As usual, choosing the security parameters represents a tradeoff between the security and the efficiency. Therefore, it also strongly depends on two things:

  • how crucial it is that no one breaks the security guarantee (if an adversary succeeds at "guessing correctly" the challenge, hence can break soundness, how dangerous is that? How strong is the incentive for an adversary to break the system? Could he e.g. become super-rich by succeeding at doing so?)
  • how widely deployed might the system become (will it be used a few times, or hundredth of thousands of time?)

A very rough rule of thumb in this case could be (note here that we are talking about a statistical success probability during a run of a protocol, things would be very different if this was instead a computational security level, e.g. the average number of operations needed to break a scheme):

When the system has initially a soundness $1/2$, and reaching a better soundness involves parallel repetition of the entire protocol:

  • If the system should be very efficient and does not protect extremely valuable resources (or alternatively, if the incentive to break the system is not huge), a basic choice could be to settle for a $2^{-40}$ success probability.
  • If the system protects very valuable goods, or if there is a very strong incentive to cheat, but getting good efficiency is also very important, settling for a $2^{-80}$ success probability should be fine.
  • If people using the system are paranoid, or achieving strong efficiency is not such a concern while security is of paramount importance, go for $2^{-128}$ success probability.
  • In all cases, divides the target success probability by the number of times the system might be used in its lifetime (or the number of tries an adversary can plausibly get). E.g. a widely deployed system can be expected to be used by, say, $2^{20}$ individuals a few times each, so divide the target success probability by at least $2^{20}$ (such that the initial number, before dividing, becomes the probability that someone eventually ends up breaking the security by chance during the lifetime of the system).

When the system has natively the possibility to use a larger challenge space (e.g. Schnorr proof):

  • in this case, dividing the success probability by $2^k$ often involves sending only $k$ more bits in the proof. When soundness is that cheap, there is no need not to settle for a completely safe security margin, without optimizing for a few bits - e.g. going for a $2^{-128}$ or $2^{-256}$ success probability looks reasonable.
$\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.