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!


  • [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.
  • 5
    $\begingroup$ I currently don't have time to write an answer, (In particular because this would involve checking in the relevant papers that my thinking is correct.) but I think this is all based on a - very understandable - misinterpretation of the black-box ZK definition. The important part is that the simulator is universal for all possible verifiers. This includes those verifiers $V^*_s$ that include hardcoded an $s\in S_n$. If the simulator could simulate the transcript of such $V^*_s$ for all $x$, then we could decide the language $L_K$ in PPT. $\endgroup$ – Maeher May 2 '19 at 9:34
  • $\begingroup$ @Maeher, Thank you so much for reading through the question, correcting my typo and presenting this counter-example. I really appreciate it. Based on your comment, I figured out the answer: I do understand the notion of universal black-box simulator correctly. My misunderstanding actually turns out to be in "non-uniformity". The $V^*_s$ you gave is non-uniform (since the length of s depends on the security parameter, so it can only hard-wired into a non-uniform adversary). But This attack is not an issue for GMR definition, which only guarantees security against uniform $V^*$. $\endgroup$ – Xiao Liang May 2 '19 at 22:15

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.


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.