# Single theorem adaptive vs non-adaptive non-interactive zero-knowledge proofs [duplicate]

I am trying to understand non-interactive zero-knowledge protocols (NIZK). But, I encountered single theorem adaptive and non-adaptive NIZK protocols. According to my understanding,

In adaptive NIZK protocols, simulator ($S$) is divided into two stages ($S_1,S_2$) where in first stage it generates the common reference string and in second stage, it generates the proof for any input using common reference string generated in first phase.

In non-adaptive NIZK protocols, given an input, simulator outputs common reference string along with the proof.

Is this understanding correct?

Is there any way to covert a non-adaptive NIZK protocol to adaptive NIZK?

What is difference between single-theorem and multi-theorem NIZK?

• As you asked a separate question on using NIZK in group signatures, and as you should avoid asking several questions at once in the same post, I'd recommend that you remove the third question in your post. – Geoffroy Couteau Jan 30 '18 at 12:15

## 2 Answers

It seems to me that the term "adaptive NIZK" is unclear. Where did you encounter it? If you give me the context, I can probably tell you what it was suppose to mean in this context.

Specifically, adaptive NIZK could refer to:

• NIZK with adaptive soundness, where the malicious prover first receives the crs as input, then produces a word and a proof, and wins if the word is not in the language yet the proof is accepted;
• NIZK with adaptive zero-knowledge, which matches what you mentioned: the simulator is divided into two parts, and first return a simulated crs, then outputs simulated proofs;
• NIZK secure against adaptive adversaries in the UC model, which is more complex.

Assuming you meant "adaptive zero-knowledge", I don't think there is any generic way of transforming non-adaptive NIZKs into adaptive NIZKs; in fact, it's an open problem to build adaptive perfect NIZK arguments from standard assumption (those we have are from non-standard "knowledge-of-exponent-type" assumptions, or satisfy only a weaker property, called adaptive culpable soundness).

For your third question, I don't know if there are group signatures that use non-adaptive NIZKs.

For the last question, in a single-theorem NIZK, the zero-knowledge property is only guaranteed for provers that send a single proof after the crs is generated - to perform more proofs, new crs must be generated. Put otherwise, the length of the crs must be proportional to a bound on the number of proofs that will be executed with this crs. In contrast, in a multi-theorem NIZK, the same crs can be reused an arbitrary (polynomial) number of times for generating proofs. There is a generic transformation from single-theorem to multi-theorem NIZKs that uses only one-way functions, see this paper.

I would start by saying that the interactivity of a ZK proof is not really anything to do with this concept of adaptivity.

Secondly, the adaptive simulator is really first providing a transcript of the conversation between a prover and verifier who each at any point in the protocol might be honest or malicious. The second part is explaining that this transcript could also be from a conversation between a prover and verifier that are always honest.