Is it better to have statistical zero-knowledge or computational zero- knowledge in a system?

If it depends, is there a slightly accurate generalisation that can be made?

Maybe one can be somewhat reduced to the other (doubt it)?

Maybe one of them solves a larger class of problems?

  • 1
    $\begingroup$ Discourse: SZK can only be broken if the protocol is ran exp amount of times/enough times to take advantage of the statistical difference. While CZK needs to be ran by an unbounded/exponential TM. Intuition is telling me that SZK is "close enough" to PZK that it does not matter, but they both seem breakable if given an unbounded TM... $\endgroup$ Aug 22 '19 at 22:49

Security-wise having statistical security is always better than computational security if the security parameter is equal. This is because statistical security ($\forall A: Pr[A(f(x)) = x] \le negl(n)$) implies computational security ($\forall B: Pr[B(f(x)) = x] \le negl(n)$) with B all algorithms in P-SPACE and A being all algorithms (which includes all algorithms in B).

However, there is a catch. In practice the security parameters differ by a large amount. While one can argue by just using the same security parameters for statiscial security and computational security, it's still a problem. This is because statistically secure functions usually use smaller security parameters compared to computationally secure functions in practice to reduce computation time and space since they aim different targets; and most statistically secure protocols are usually not designed to be used as functions with computational security (but it's not impossible doing so either; the Fiat-Shamir transformation is one example since it can transform interactive zero-knowledge proofs with statistical security into non-interactive proofs with computationally security secure in the Random Oracle Model).

Typically you want to archive different targets with statistical security and computationally security:

  • Statistical secure functions are usually used in interactive settings which are repeated fixed times. For example, think about lotteries. If one could repeat a lottery unlimited times for free at any time, everyone would be winning. But in reality you can participate in a lottery only once per week and you need to pay per participation.
  • Computational security functions usually deals with algorithms which try to extract a secret x out of the information y (and have some additional power I skip here). The adversary is allowed to use any stragegy he wants, but is limited to the time and space. Because the problem is that 'hard' (being in NP) the adversary still is unlikely to be successfull, unless he is very lucky.

In the protocols which implement secure functionality computational security and statistical security are differentiated if both are needed since the security parameters do differ in practice.


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.