Complexity classes for proofs of knowledge

Question

Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes like SZK and NISZK are extremely natural from a complexity standpoint, even if we forgot entirely about zero knowledge and just defined them in terms of their complete promise problems. By contrast, on googling 'proofs of knowledge,' I was surprised not to find any papers or lecture notes discussing this lovely concept in terms of complexity classes.

To give some examples: what can one say about the subclass of SZK∩MA∩coMA consisting of all languages L that admit statistical zero-knowledge proofs for x∈L or x∉L, that are also proofs of knowledge of a witness proving x∈L or x∉L? Certainly this class contains things like discrete log, but we couldn't prove that it contains graph isomorphism without putting GI in coMA. Does the class encompass all of SZK∩MA∩coMA? One could also ask: if one-way functions exist, then does every language L∈MA∩coMA admit a computational zero-knowledge proof, that's also a proof of knowledge of a witness proving x∈L or x∉L? (My apologies if one or both of these have trivial answers---I'm just trying to illustrate the sort of thing one could ask, once one decided to look at PoK in complexity-theoretic terms.)

Answer 1

This is not an actual answer; I'm just sharing some results (which do not fit in one comment).

1. Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge proof of language membership (assuming OWFs exist). To this end, their presented a ZK proof for graph 3-colorability. Later, Bellare and Goldreich (CRYPTO '92) proved that this ZK proof is also a ZK proof of knowledge (PoK). Using Levin reductions (see footnote 12 of the former paper), Every language in NP has a ZK PoK (assuming OWFs exist).
2. Itoh and Sakurai (ASIACRYPT '91) have a paper on complexity-theoretic results regarding relations having constant-round ZK PoK.
3. This is a seemingly unrelated result, though I can't help noticing some similarities. I somehow feel (not anything formal) that proof of membership vs. proof of knowledge is similar to decision vs. search. Perhaps in this sense, one can also cite the work of Bellare and Goldwasser (J. Computing, 1994), where they (conditionally) prove that not all languages in NP have a reduction from search to decision.

Some open problems (perhaps solved, but not that I know of) regarding complexity-theoretic aspects of PoKs:

1. Various efficiency measures for ZK PoKs of a specific relation with certain complexity (e.g., a relation in AM):

   • Communication complexity of the proof
   • Computational complexity of the parties
   • Knowledge tightness (i.e., the ratio between the (expected) running time of the simulator and the running time of the verifier in the real interaction)

2. Complexity of relations admitting ZK PoK with certain limitations, say limited round complexities (Itoh and Sakurai only consider constant-round ZK PoK). Another example is when the prover is polynomial time: He cannot use the reduction to 3-colorability, as he cannot solve NP-complete relations. All NP-complete problems have a Cook reduction from search to decision. Yet, by Bellare-Goldwasser result cited above, such reductions do not necessarily exist for all NP languages/relations.

3. Other interesting results regarding PoKs which are not necessarily ZK, but whose knowledge complexity is otherwise limited. See Goldreich and Petrank (Comput. complex., 1999).

Before concluding, allow me to mention that there are actually several definitions for PoKs, some of which are cited below:

1) Early attempts: Feige, Fiat and Shamir (J. Cryptology, 1988), Tompa and Woll (FOCS 1987), and Feige and Shamir (STOC 1990).

2) De facto standard: Bellare and Goldreich (CRYPTO '92). This paper surveys the early attempts at defining PoKs, observes their shortcomings, and suggests a new definition which can be considered as "the" definition of PoK. This definition has a black-box nature (the knowledge extractor has black-box access to the cheating prover).

3) Conservative PoKs: Defined by Halevi and Micali (ePrint Archive: Report 1998/015), this definition augments the previous definition to guarantee prover feasibility. It also gives a definition for the knowledge of a single prover, which is good when answering the question "what does it mean to say that P knows something?"

4) Arguments of Knowledge with Non Black-Box Extraction: As mentioned above, the standard definition of PoKs is black box, which makes it impossible to have resettable zero-knowledge proofs (or arguments) of knowledge for non-trivial languages. Barak et al. (FOCS 2001) provide a non-black-box definition, which is based on (but differs from) the definition of Feige and Shamir (STOC 1990) cited above.