Non interactive zero knowledge proof

Definition

Originally, non-interactive zero-knowledge was only defined as a single theorem proof system. In such a system each proof requires its own fresh common reference string. A common reference string in general is not a random string. It may, for instance, consist of randomly chosen group elements that all protocol parties use. Although the group elements are random, the reference string is not as it contains a certain structure (e.g., group elements) that is distinguishable from randomness. Subsequently, Feige, Lapidot, and Shamir introduced multi-theorem zero-knowledge proofs as a more versatile notion for non-interactive zero knowledge proofs.

In this model the prover and the verifier are in possession of a reference string sampled from a distribution, D, by a trusted setup σ ← S e t u p ( 1 k ) . To prove statement y ∈ L with witness w, the prover runs π ← P r o v e ( σ , y , w ) and sends the proof, π , to the verifier. The verifier accepts if V e r i f y ( σ , y , π ) = a c c e p t , and rejects otherwise. To account for the fact that σ may influence the statements that are being proven, the witness relation can be generalized to ( y , w ) ∈ R σ parameterized by σ .

Completeness

Verification succeeds for all σ ∈ S e t u p ( 1 k ) and every ( y , w ) ∈ R σ .

More formally, for all k, all σ ∈ S e t u p ( 1 k ) , and all ( y , w ) ∈ R σ :

Soundness

Soundness requires that no prover can make the verifier accept for a wrong statement y ∉ L except with some small probability. The upper bound of this probability is referred to as the soundness error of a proof system.

More formally, for every malicious prover, P ~ , there exists a negligible function, ν , such that

The above definition requires the soundness error to be negligible in the security parameter, k. By increasing k the soundness error can be made arbitrary small. If the soundness error is 0 for all k, we speak of perfect soundness.

Multi-theorem zero-knowledge

A non-interactive proof system ( S e t u p , P r o v e , V e r i f y ) is multi-theorem zero-knowledge, if there exists a simulator, S i m = ( S i m 1 , S i m 2 ) , such that for all non-uniform polynomial time adversaries, A ,

Here S i m ( σ , τ , y , w ) outputs S i m 2 ( σ , τ , y ) for ( y , w ) ∈ R σ and both oracles output failure otherwise.

Pairing-based non-interactive proofs

Pairing-based cryptography has led to several cryptographic advancements. One of these advancements is more powerful and more efficient non-interactive zero-knowledge proofs. The seminal idea was to hide the values for the evaluation of the pairing in a commitment. Using different commitment schemes, this idea was used to build zero-knowledge proof systems under the sub-group hiding and under the decisional linear assumption. These proof systems prove circuit satisfiability, and thus by the Cook–Levin theorem allow proving membership for every language in NP. The size of the common reference string and the proofs is relatively small; however, transforming a statement into a boolean circuit incurs considerable overhead.

Proof systems under the sub-group hiding, decisional linear assumption, and external Diffie–Hellman assumption that allow directly proving the pairing product equations that are common in pairing-based cryptography have been proposed.

Under strong knowledge assumptions, it is known how to create sublinear-length computationally sound proof systems for NP-complete languages. More precisely, the proof in such proof systems consists only of a small number of bilinear group elements.