In this paper on pg. 1241 the authors discuss bullet point on Adaptive Zero-Knowledge : 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.

• 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
– rath
Nov 24, 2013 at 17:51
• 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}$. $\;\;\;\;\;\;\;$
– user991
Nov 24, 2013 at 22:02

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.

• Extremely helpful Nov 24, 2013 at 22:46