Most modern papers on zero-knowledge proofs (for example, BBB+16) recycle essentially the same list of boilerplate definitions, concerning soundness (formulated using extraction or some form of "emulation") and zero-knowledge (involving simulation).

Yet Katz and Lindell's incredible book does not use these definitions—instead speaks only of an Identification scheme (see [KL15, p. 452]), which is either secure (against a passive attack), or isn't (i.e., see Def. 12.8). For example, the Schnorr protocol is formulated only as an identification scheme (Fig. 12.2). Moreover, both its perfect zero knowledge and 2-soundness are implicitly contained in its proof of security (Thm. 12.11).

My question is: should I view this simpler Identification scheme-based definition as "the future"? Can we get by with definitions of this sort, i.e., can this definition capture everything we "care about" in zero-knowledge proofs? What are the reasons for keeping the more traditional definitions around, if any?

Moreover, has an Identification scheme-based definition been formulated for more general settings, where the "statement" of the relevant NP language has a complicated structure (is no longer uniformly random, maybe selected by the adversary, etc.)? Where can I find these more general formulations?

  • $\begingroup$ I'd suppose the book contains this simpler definition for the sake of understandability and to avoid having to introduce zk-proofs as well as simulation based proofs. $\endgroup$ – SEJPM Dec 16 '19 at 5:06

I think I'm qualified to answer this question :-). The approach of going via identification schemes suffices for constructing secure signature schemes. Since this is the aim of this part of the book, it is much simpler than doing full blown zero knowledge. However, if you are interested in looking at sigma protocols and compilation to non-interactive zero knowledge via Fiat-Shamir, then you are going to need the more complex definitions. So, in short, what we do in the book is not more general; on the contrary, it's more specific, but suffices for what we need.

  • $\begingroup$ Thanks Prof. Lindell! I'm still not 100% clear on what is lost under the simpler definition. In any case I think the community would love to see a Vol. II, where you treat zero-knowledge proofs and secure computation. $\endgroup$ – BD107 Dec 20 '19 at 15: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.