What is the difference between Special Honest Verifier Zero-Knowledge (SHVZK) and Honest Verifier Zero-Knowledge (HVZK)? Sometimes I see one term being used, other times the other. Do they mean the same thing?


Special Honest Verifier Zero-Knowledge is a particular case of Honest Verifier Zero-Knowledge; that is, if a protocol satisfies SHVZK, it satisfies HVZK. SHVZK has been introduced to simplify discussions about $\Sigma$-protocols. In $\Sigma$-protocols, HVZK is typically proven as follows: fix an arbitrary challenge $e$, and show that it is possible to efficiently generate a random transcript $(c, e', a)$ for a $\Sigma$-protocol, conditioned on $e = e'$. If such a simulator can be exhibited, then the $\Sigma$-protocol is clearly HVZK. The term SHVZK refers to $\Sigma$-protocols where this particular condition holds.

Note that similarly, the term special soundness is generally used to refer to a sufficient property for the soundness of a $\Sigma$-protocol (typically, that given two transcripts $(c,e,a)$ and $(c,e',a')$ for the same $c$, it is possible to extract a witness efficiently), which is typically satisfies by most $\Sigma$-protocols. Each time, "special XXX" simply means "a specific notion which is sufficient for XXX".

  • $\begingroup$ Thank you, @Geoffroy Couteau! Btw, is there any literature (book, paper, etc) that introduces and explains in an intermediate level the different approaches to security proofs in cryptography? $\endgroup$ – Fiono Sep 22 '20 at 20:33
  • $\begingroup$ Hmm, maybe? Unfortunately, I'm not really aware of the basic crypto books and teaching documents, I never used any myself (I learned by reading research articles), and "security proofs in cryptography" is an extremely vast subject. Lindell's tutorial on simulation is one important example that comes to mind about the simulation technique, a very general and important proof method. The paper might provide other pointers. I am also personally fond of Goldreich's books (Foundations of Cryptography Vol. 1 & 2), but some find them hard to read. $\endgroup$ – Geoffroy Couteau Sep 23 '20 at 13:08
  • $\begingroup$ Ty, @Geoffroy Couteau! Yes, I am also learning by reading research articles. But its not easy when the information is disperse and sometimes even looks contradicting. I think there is a need for a central piece of information at intermediate level that serves as a general guide for "security proofs in cryptography" to attract more new people to the field, not only the smart ones :p maybe I'll write one myself! $\endgroup$ – Fiono Sep 29 '20 at 10:06

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.