 Noninteractive zeroknowledge proof

Noninteractive zeroknowledge proofs are a variant of zeroknowledge proofs. Blum, Feldman, and Micali ^{[1]} showed that a common reference string shared between the prover and the verifier is enough to achieve computational zeroknowledge without requiring interaction. Goldreich and Oren^{[2]} gave impossibility results for one shot zeroknowledge protocols in the standard model. These two results are not contradictory, as the impossibility result of Goldreich and Oren does not hold in the common reference string model or the random oracle model. Noninteractive zeroknowledge proofs however show a separation between the cryptographic tasks that can be achieved in the standard model and those that can be achieved in 'more powerful' extended models.
The model influences the properties that can be obtained from a zeroknowledge protocol. Pass^{[3]} showed that in the common reference string model noninteractive zeroknowledge protocols do not preserve all of the properties of interactive zeroknowledge protocols, e.g. they do not preserve deniability.
Noninteractive zeroknowledge proofs can also be obtained in the random oracle model using the FiatShamir heuristic.
Contents
Definition
Originally^{[1]}, noninteractive zeroknowledge 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^{[4]} introduced multitheorem zeroknowledge proofs as a more versatile notion for noninteractive 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 . To prove statement with witness w, the prover runs and sends the proof π to the verifier. The verifier accepts if Verify(σ,y,π) = accept, and rejects otherwise. To account for the fact that σ may influence the statements that are being proven, the witness relation can be generalized to parameterized by σ.
Completeness
Verification succeeds for all and every .
More formally, for all k, all , and all :
Soundness
Soundness requires that no prover can make the verifier accept for a wrong statement 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 , 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.
Multitheorem Zeroknowledge
A noninteractive proof system (Setup,Prove,Verify) is multitheorem zeroknowledge, if there exists a simulator Sim = (Sim_{1},Sim_{2}) such that for all nonuniform polynomial time adversaries ,
Here Sim(σ,τ,y,w) outputs Sim_{2}(σ,τ,y) for and both oracles output failure otherwise.
Pairingbased Noninteractive Proofs
Pairingbased cryptography has led to several cryptographic advancements. One of this advancements are more powerful and more efficient noninteractive zeroknowledge 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 zeroknowledge proof systems under the subgroup hiding^{[5]} and under the decisional linear assumption.^{[6]} These proof systems prove circuite satisfiability, and thus by the Cook–Levin theorem allow to prove 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 causes a considerable overhead.
Proof systems under the subgroup hiding, decisional linear assumption, and external DiffieHellman assumption that allow to directly proof the pairing product equations that are common in Pairingbased cryptography have been proposed.^{[7]}
References
 ^ ^{a} ^{b} Manuel Blum, Paul Feldman, and Silvio Micali. NonInteractive ZeroKnowledge and Its Applications. Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC 1988). 103112. 1988
 ^ Oded Goldreich and Yair Oren. Definitions and Properties of ZeroKnowledge Proof Systems. Journal of Cryptology. Vol 7(1). 132. 1994 (PS)
 ^ Rafael Pass. On Deniability in the Common Reference String and Random Oracle Model. Advances in Cryptology  CRYPTO 2003. 316337. 2003 (PS)
 ^ Uriel Feige, Dror Lapidot, Adi Shamir: Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29(1): 128 (1999)
 ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Perfect Noninteractive Zero Knowledge for NP. EUROCRYPT 2006: 339358
 ^ Jens Groth, Rafail Ostrovsky, Amit Sahai: Noninteractive Zaps and New Techniques for NIZK. CRYPTO 2006: 97111
 ^ Jens Groth, Amit Sahai: Efficient Noninteractive Proof Systems for Bilinear Groups. EUROCRYPT 2008: 415432
External links
Categories: Cryptographic protocols
 Theory of cryptography

Wikimedia Foundation. 2010.
Look at other dictionaries:
Zeroknowledge proof — In cryptography, a zero knowledge proof or zero knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.A… … Wikipedia
Zeroknowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Zero knowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Preuve zeroknowledge — Preuve à divulgation nulle de connaissance Une preuve à divulgation nulle de connaissance est un concept utilisé en cryptologie dans le cadre de l authentification et de l identification. Cette expression désigne un protocole sécurisé dans lequel … Wikipédia en Français
Interactive proof system — In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to… … Wikipedia
Proof of knowledge — In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds convincing a verifier that it knows something. What it means for a machine to know something is defined in terms of computation. A machine knows something … Wikipedia
Parity of zero — Zero objects, divided into two equal groups Zero is an even number. In other words, its parity the quality of an integer being even or odd is even. Zero fits the definition of even number : it is an integer multiple of 2, namely 0 × 2. As a… … Wikipedia
Charles Rackoff — Born 26 November 1948 New York City Fields Cryptology Institutions … Wikipedia
Charles Rackoff — Charles Weill Rackoff (* 26. November 1948 in New York City) ist ein US amerikanischer Informatiker und Kryptograph. Rackoff studierte am Massachusetts Institute of Technology, wo er 1974 bei Albert Ronald da Silva Meyer promoviert wurde (The… … Deutsch Wikipedia
Standard Model (cryptography) — In cryptography the standard model is the model of computation in which the adversary is only limited by the amount of time and computational power available. Other names used are bare model and plain model.Cryptographic schemes are usually based … Wikipedia