Contradiction to the Sequential Self-Composability of Black-Box Zero-Knowledge?

Question

---

In short: it is well-known that black-box zero-knowledge protocols are sequentially self-composable. However, Goldreich and Krawczyk [GK90] present a protocol which is proven to be zero-knowledge (in a black-box manner to me), but NOT sequentially self-composable. This seems like a paradox to me. I elaborate on this question below.

---

The concept of zero-knowledge proofs is originally defined in [GMR85]. But this definition is not closed under sequential self-composition. To solve this problem (and to seek for a more appropriate definition) [GO94] proposes black-box ZK and auxiliary-input ZK and shows the relations between these definitions. In this question, I will use the following abbreviations to ease the presentation.

• GMR: the class of protocols satisfying the original definition of ZK in [GMR85]
• BBZK: the class of protocols that are black-box zero-knowledge as defined in [GO94]
• AuxZK: the class of protocols that are Auxiliary-input ZK as defined in [GO94]

[GO94] proves the following relation: BBZK $\subsetneq$ AuxZK $\subsetneq$ GMR.

[GO94] also proves that AuxZK is closed under sequential self-composition.

In [GK90], a protocol that satisfies GMR but is NOT sequentially self-composable is constructed to separate AuxZK from GMR. However, that protocol appears to be BBZK to me. My understanding shouldn't be correct, because BBZK $\subsetneq$ AuxZK (thus BBZK protocol must also be sequentially self-composable). So, I feel that I must have missed some important aspects about the proof.

I know that this may not be a valuable question since the definition of ZK is already well-established, but it kind of bothers me... So I would appreciate it a lot if someone can correct my misunderstanding.

In the following, I will briefly describe that protocol and explain why I think it is BBZK.

That protocol is based on P-evasive pseudorandom sets. Roughly speaking, P-evasive pseudorandom ensembles are a sequence of sets $\{S_n\}_n$ such that $S_n$ and $\{0,1\}^{4n}$ are computationally indistinguishable, and any PPT adversary can find an element in $S_n$ with only negligible probability (the negligible function is of $n$, which can be treated as the security parameter).

They also need a hard Boolean function $K(\cdot)$ such that the language $L_K = \{x: K(x) = 1\}$ is not in BPP.

With the above two tools (their existence was proven in [GK90]), the protocol works as follows to prove a statement in the trivial language $x \in L = \{0,1\}^*$ (i.e., every binary string $x$ is a true statement):

• Round 1: $V$ sends $s$
• Round 2: If $s \in S_n$, $P$ sends $K(x)$; otherwise, $P$ sends an $s_0\in S_n$.
• Verifier's Decision: $V$ always accepts.

Completeness and soundness is obvious. This protocol is not sequentially self-composable: consider two sequentially execution of it. $V^*$ can just use the $s_0$ (that he obtains from the first execution) as the Round-2 message in the second execution to learn $K(s_0)$, which is hard such that no PPT simulator can simulate.

Zero-Knowledge: to prove it is GMR zero-knowledge (in the stand-alone setting), they construct a simulator that always picks a random string from $\{0,1\}^{4n}$ as the simulated Round-2 message. By the pseudorandomness of $S_n$, this simulation is computationally indistinguishable from a (single-time) real execution. The only problematic case is the one where $V^*$ picks an $s\in S_n$ as his Round-1 message, where the simulator need to compute $K(s)$, which is infeasible. But this only happens with negligible probability since $S_n$ is P-evasive.

My question is: in the above proof for Zero-Knowledge, it seems the simulator only uses $V^*$ in a black-box manner, namely, this protocol seems BBZK. If so, this contradicts the fact that BBZK is sequentially self-composable. Hope that someone can correct my misunderstanding. Thank you!

References:

• [GMR85] S Goldwasser, S Micali, and C Rackoff. 1985. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (STOC '85). ACM, New York, NY, USA, 291-304.
• [GK90] Goldreich, Oded, and Hugo Krawczyk. "On the composition of zero-knowledge proof systems." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 1990.
• [GO94] Goldreich, Oded, and Yair Oren. "Definitions and properties of zero-knowledge proof systems." Journal of Cryptology 7.1 (1994): 1-32.

Answer 1

This answer is derived from the comment of @Maeher. All credit should go to Maeher. Also, thanks to @Occams_Trimmer for attracting more attention to this question.

Maeher shows a dishonest verifier $V^*_s$ for which the simulation technique in the question fails. $V^*_s$ has a value $s \in S_n$ hard-coded inside. It then ignores its random tape and simply sends the hard-coded value $s$ as the Round-1 message. So the simulator $M^{V^*_s}$ is forced to respond with $K(s)$, which no PPT machine can compute. Thus, $M^{V^*_s}$ cannot finish the simulation successfully.

Notice that there is an implicit-yet-important aspect in the above argument: $V^*_s$ must be non-uniform. Otherwise, it cannot have $s$ hard-coded inside when the security parameter grows. In another words, the above attack happens only if we consider ZK property against non-uniform adversaries. But the GMR definition only guarantees ZK against uniform adversaries (PPT Turing machines). Thus, the proof (in the above question) for ZK property w.r.t. GMR definition still goes through. However, the definition of AuxZK essentially guarantees security against non-uniform $V^*$ (because $V^*$ now has an auxiliary tape and any non-uniform advice can be put on this auxiliary tape). The same holds for BBZK as it is a subset of AuxZK. So the proof in the question fails if one wants to prove the black-box Zero-Knowledge property.

In summary, although the proof in the question is done in a black-box manner, it is only for uniform adversaries, which is not enough to give us BBZK (or even AuxZK). Thanks to Maeher for making this point clear.