Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
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 '13 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}$. $\;\;\;\;\;\;\;$ –  Ricky Demer Nov 24 '13 at 22:02
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
Extremely helpful –  user1068636 Nov 24 '13 at 22:46
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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