Non-trivial examples of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge

Question

It got me confused these days when I encountered the notions of zero-knowledge proofs (ZKP) and zero-knowledge proofs of knowledge (ZKPoK). As far as I know, the two terms are not the same, but all the ZKP systems I know so far also happen to be ZKPoK systems.

Can anyone tell me if there is any non-trivial example of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge, and vice versa?

Answer 1

At first, every ZKPoK protocol is ZKP protocol. This is obvious: if you proved that you know a witness, therefore a witness exists, therefore the statement belongs to the language.

The interesting question is whether a protocol exists which is ZKP but not ZKPoK. It holds for trivial languages, but you're justly not satisfied with this. My idea in a discrete log settings, similar to Schnorr protocol, is the following: take a protocol proving the equality of the discrete logarithms of $y_1$, $y_2$ to bases $g, h \in G$, i.e. for a language $\{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w \}$, where $w\in Z_q$ is a witness. $G$ is cyclic group here.

The classical Schnorr-like protocol for that is the following:

1. Prover chooses $k\in Z_q$, calculates $C_1=g^k, C_2=h^k$ and sends $C_2, C_2$ to Verifier.

2. Verifier chooses $e\in Z_k$ and sends it to Prover.

3. Prover calculates $r = k + ew$ and sends it to Verifier.

4. Verifier checks: $C_1 y_1^e = g^r$ and $C_2 y_2^e = h^r$.

You can easily build knowledge extractor E which will extract $w$ (just the same as in Schnorr protocol), so this is clearly ZKPoK protocol for a language $L_1 = \{ g||h||y_1||y_2 : \exists w, y_1 = g^w \land y_2 = h^w \}$.

But, notice that this is also a ZKP for a language $L_2 = \{ g||h||y_1||y_2 : \exists v, h = g^v \land y_2 = y_1^v \}$. The language is actually the same ($L_1 = L_2 = L$), but it's defined through another witnesses. And knowing a witness $w$ doesn't help you to find witness $v$. So, this protocol is not a ZKPoK for $L_2$, while it's ZKP for it.

The trick we did here is in the following. We have a language which could be independently defined by two types of witnesses. You can use say the witness of the first type to provide a proof, but you could not know the witness of the second type. You can say that it's just a trick and this protocol is still a ZKPoK, just for another type of witness. You're right, but this trick is inevitable: if a prover can provide a proof, and the language is not trivial, the prover necessarily knows something special (otherwise, anybody can conduct such proofs for himself, and language becomes trivial! ). And this special thing is a witness! But, this could be another type of witness, not that one which you initially supposed. This is a core idea of the trick.

WARNING: this is an improvisation and I'm not 100% sure in this, so please wait for endorsement of other people.

Answer 2

This is a nice question, and I don't know any natural examples of interactive zero-knowledge proof systems which are not proofs of knowledge, although they are bound to exist. The (rewinding based) proofs I recall ensure soundness in a way which allows extraction. That being said, for the non-interactive setting, the situation is quite different, and there are several examples which are not known (and very unlikely) to be extractable under standard assumptions (i.e. not using knowledge of exponents or the like).

The best example (although not ZK proofs) are hash proof systems/smooth projective hash functions which are used in the Cramer--Shoup IND-CCA secure construction. There is no knowledge involved. From this, Kiltz--Wee construct a (quasi-adaptive) NIZK. These are for special languages though and not proofs, i.e. not unconditionally sound.

An example NIZK arguments for all of NP are Groth--Sahai proofs. Perfect zero-knowledge cannot be extractable in the non-interactive setting. There is also a non-interactive witness-indistinguishable NIWI version of Groth--Sahai proofs, which is weaker than NIZK, but does not need a CRS. (NIWI only guarantees that you cannot distinguish two (valid) witnesses $w, w'$ of a statement, but may otherwise learn information about $w$.) They are not extractable.
Similarly, the Feige--Lapidot--Shamir [FLS] NIWI is not extractable (but needs the hidden bits model).

Non-extractable NIZK or NIWI, can be (stupidly) converted to interactive non-extractable ZK proofs: First send an perfectly binding commitment to the NIWI proof, and then prove in zero-knowledge that a NIWI verifier would accept. Alternatively, use MPC to construct the CRS.

If you allow arguments, i.e. computational soundness, using the OR-trick from FLS gives you a more natural construction from NIWI:

1. V sends y = OWF(s)
2. P sends d = Com(0) and Com(NIWI: $x \in L \lor (d = Com(s) \land y = OWF(s))$)
3. V reveals s
4. P reveals NIWI
5. V accepts if NIWI verifies

Not formally proven, but plausible: By hardness of the OWF, and binding of Com, cheating for P is computationally hard. By hiding of Com, a simulator can rewind from step 3 to 2, and commit to the preimage s in d, and prove the OR-branch, instead of $x \in L$.