1
$\begingroup$

Is honest verifier zero knowledge closed under sequential composition? My guess is that since the verifier has to throw random challenges, they cannot adapt their challenge from the transcripts of a prior HVZK and thus cannot learn any additional information?

$\endgroup$
6
  • $\begingroup$ If Fiat-Shamir is used, can we argue in the way that: given two HVZK proof instances are convereted to NIZK using Fiat-Shamir, then the sequential composition of two NIZK is closed given ZK (with auxiliary input) is closed under sequential composition? $\endgroup$
    – Sean
    Aug 29 '20 at 1:51
  • $\begingroup$ What does that mean "HVZK is closed under sequential composition"? It does not make sense to me. "HVZK" is the class of all language that have honest-verifier zero-knowledge proof, but saying that a class of language is closed under sequential composition does not make sense - you can compose protocols, not languages. Are you asking if sequentially composing an HVZK protocol with himself still leads to an HVZK protocol? (if this is your question, the answer is yes) $\endgroup$ Sep 24 '20 at 17:22
  • $\begingroup$ That's right. Sequentially composing HVZK protocols (just like sequentially composing perfect ZK protocols). Is it still closed? $\endgroup$
    – Sean
    Sep 26 '20 at 13:31
  • $\begingroup$ The sequential composition of HVZK protocols is still HVZK, yes. I'm not sure the term "closed" is appropriate when talking about protocols; it is when talking about a class of languages, which is not what you are doing here. $\endgroup$ Sep 28 '20 at 7:07
  • 1
    $\begingroup$ 2 cents by a rookie (me) about the the term "closed" @GeoffroyCouteau : in section 4.3.4 of Foundations of Cryptography vol 1 Oded Goldreich writes: "An intuitive requirement that a definition of zero-knowledge proofs must satisfy is that zero-knowledge proofs should be closed under sequential composition. [...] Interestingly, zero-knowledge proofs as defined in Definition 4.3.2 are not closed under sequential composition, and this fact is indeed ..." $\endgroup$
    – baro77
    Oct 16 at 20:42
1
$\begingroup$

Consider an interactive argument $(P,V)$ for witness relation $R\subseteq X\times W$. A argument is honest verifier zero knowledge if there exists a probabilistic polytime simulator $S$ such that for all $(x,w)\in R$, the following probability distributions (on the randomness of $P$ and $V$) are close: $$S(x)\approx\text{View}_V(P(x,w),V(w))$$ For $t$-sequential composition, the simulator can invoke the simulator $S$ $t$ times over the $t$ relation pairs. In fact, HVZK is also closed the stronger notion of parallel composition.

Informally, this simulator suffices because the verifier must behave honestly; thus, it cannot adapt its queries based upon auxillary information (often denoted as an auxillary input called an advice string).

For a more in-depth discussion, consider reading the following works:

  1. https://www.wisdom.weizmann.ac.il/~oded/PSX/oren.pdf
  2. https://www.wisdom.weizmann.ac.il/~oded/PSX/zk-comp.pdf
$\endgroup$

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.