GMR88 (Goldwasser, Micali, Rackoff) in chapter 3 mentions that computational zero knowledge, in comparison to statistical or perfect zero knowledge is the most general amongst the three definitions.

Why is that the case? Why isn't perfect zero knowledge the most general notion of zero knowledge?


Because being perfectly zero-knowledge is a more stringent security requirement.

For a language to have a perfect zero-knowledge proof, you need to exhibit a proof of membership to the language so that the proof can be simulated perfectly without knowing the witness; i.e., even an unbounded adversary should not be able to see any difference between the real proof and the simulated proof. Hence, you are requiring a very strong security notion: security against an adversary with unlimited computational power.

Computational zero-knowledge, on the other hand, only requires that the simulated proof cannot be distinguished from the real proof by a computationally bounded adversary. This is a weaker security notion, hence easier to achieve.

If a language has a perfect zero-knowledge proof, then it has a computational zero-knowledge proof (the same one: if it's secure against unbounded adversaries, it's in particular secure against bounded adversaries). We do not know about the converse, and we suspect that it is not true (i.e., some languages can have a computational zero knowledge proof, but no perfect zero-knowledge proof). Hence, computational zero-knowledge is more general, because more languages can have such proofs. Denoting CZK / SZK / PZK the class of languages with computational / statistical / perfect zero-knowledge proofs, we clearly have PZK $\subset$ SZK $\subset$ CZK. Furthermore, we also know that if one-way functions exist, CZK $=$ IP $=$ PSPACE, which is immensely powerful.

| improve this answer | |
  • $\begingroup$ thank you so much! mind expanding a bit more why SZK is in CZK? $\endgroup$ – graphtheory92 May 25 '18 at 2:33

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.