In this paper on pg. 1241 the authors discuss bullet point on Adaptive Zero-Knowledge :

enter image description here

I am new to Zero-Knowledge and I am having trouble understanding what they are saying.

I think they are saying the probability an adversary A in the real world wins and the probability an adversary in the ideal world wins are close (negligible). But I don't know what the difference is between S and S' or what $S^{crs}$ or $S^{proof}$ are.

Also, when they use notation like $A^{S'(crs,trap,.,.)}$ is really confusing - I have no idea what this means.

I'm not looking for a complete breakdown of what this means - but if someone could even summarize what the importance of adaptive zero-knowledge that would be great.

  • 1
    $\begingroup$ Please consider manually typing the relevant text instaed of adding a screenshot. The reason for this is that the relevant text won't be picked up by the search engine if someone else is looking for something similar. Cheers $\endgroup$
    – rath
    Nov 24, 2013 at 17:51
  • $\begingroup$ Note that they give the wrong definition of proof-of-knowledge. $\;\;\;$ The pair of consecutive lines that $\;\;\;$ begins with $\:\operatorname{Pr}[\:$ and ends with $\:\operatorname{negl}(k),\:$ should be for every (i.e., not necessarily ppt) adversary $\mathcal{A}$. $\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Nov 24, 2013 at 22:02

1 Answer 1


Ok, here we are speaking of non-interactive zero-knowledge proof systems for some language $L\in NP$. We there have a pair $\sf (P,V)$ of probabilistic polynomial time algorithms (called the prover and the verifier) where both have input $x\in L$ and $\sf P$ additionally holds a secret witness $w$ for membership of $x$ in $L$ and wants to convince a verifier $\sf V$ of this fact without revealing $w$.

One requires (a bit informal):

  • correctness: for $x\in L$ all proofs generated by $\sf P$ will always be accepted by $\sf V$
  • soundness: for $x\notin L$ proofs generated by by $\sf P$ will only be accepted with negligible probability by $\sf V$
  • zero-knowledge: for $x\in L$ the view of a verifier can be efficiently simulated without the knowledge of $w$. Actually, the definitions you provide are in the common reference string (CRS) model, i.e., there is a $crs$ to which all entities have access to. For zero-knowledge one requires that $(crs,x,\pi)$ with $\pi \leftarrow {\sf P}(crs,x,w) $ and $(crs,x,\pi)$ with $(crs,\pi) \leftarrow {\cal S}(x)$, where $\cal S$ is the so called simulator, are computationally indistinguishable.

Now, adaptive zero-knowledge means, that soundness and zero-knowledge are with respect to adaptive adversaries. For soundness this means that an adversary $\cal A$ is allowed to choose $x\notin L$ after seeing the $crs$. For zero-knowledge one requires from the simulator $\cal S$, that $\cal S$ has to output $crs$ first and afterwards produce the simulated proof $\pi$. These two steps of the simulator are denoted as ${\cal S}^{crs}$ and ${\cal S}^{proof}$ respectively. Note that these two definitons are stronger definitions than in the static setting (described in the beginning).

Since the authors are talking about zero-knowledge proofs of knowledge for some $NP$ relation $\cal R$, they additionally require a property known as knowledge extraction. Basically this means that the witness $w$ can be extracted from the proof transcript (this extractor is the algorithm $E$).

They also use a common reference string $crs$ with a trapdoor $trap$ which is required in order for ${\cal S}^{proof}$ to simulate a proof without knowing the secret witness (you may look for instance at Groth-Sahai NIZK proof system for examples).

The notation ${\cal A}^{S'(crs,trap,\cdot,\cdot)}$ means that the adversary $\cal A$ has oracle access to the algorithm $S'$ where the inputs $crs$ and $trap$ are fixed and the latter two input arguments (indicated by $\cdot$) can be arbitrarily chosen by $\cal A$. Hope that helps a bit.

  • $\begingroup$ Extremely helpful $\endgroup$ Nov 24, 2013 at 22:46
  • $\begingroup$ Can the definition for adaptive zero-knowledge be rephrased in therms of computational indistinguishably, like the one for regular zero-knowledge (to make a clearer analogy)? $\endgroup$ Nov 23, 2022 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.