Zero-knowledge proof

From CRYPTUTOR

Jump to: navigation, search

This page is under construction. Do not rely on its accuracy until it is finished. Please edit this page or use the talk page to leave comments.

A Zero Knowledge proof system is an interactive proof system using which a prover Alice can convince a distrusting verifier Bob of the correctness of a statement, but without revealing anything further. Bob needs the guarantee that Alice should not be able to convince him of a wrong statement, but Alice requires the guarantee that Bob learns nothing more from the protocol than if he simply accepted her word for the truth of the statement. The latter guarantee is formalized using a simulation argument: whatever Bob could do after taking part in the protocol, he could do the same (using an alternate strategy) had he just taken Alice's word for the correctness of the statement.

Contents

[edit]

An Illustrative Example For Zero Knowledge Proof

Suppose there are two brands soft-drink which are widely believed to be the same drink in different packaging. But Alice has discovered a test to distinguish between the two, and now would like to convince Bob that the two drinks are not the same. A trivial way to prove it would be for Alice to send the details of her test to Bob and let him carry out the test himself. But suppose Alice does not want to divulge anything about her secret test. She could still convince Bob using the following protocol instead:

Bob takes a can of soft-drink of each brand. He randomly chooses a can, pours some drink out of it (all in private), and gives it to Alice. Alice then tests the sample and tells Bob which brand the sample belongs to. They iterate this procedure several times (say 100 times), each time Bob independently choosing a can to take the sample from. If Alice answers correctly in all the trials, then Bob will accept her claim that the drinks are not identical.

In this protocol, firstly, if the drinks are different and Alice has a reliable test to distinguish between them, then she can always convince Bob. On the other hand, if indeed the drinks from both the cans are identical, then Alice cannot tell them apart. Since Bob picks a can at random, the probability of Alice pointing to the right can in any iteration is exactly 0.5. The probability that Alice points to the right can every time is 2 − 100, and this is the minuscule probability with which Bob will accept Alice's claim. Finally, in this protocol Bob learns nothing from Alice's answers (at least as long as both of them follow the protocol honestly), as Bob can correctly predict her answer in every iteration assuming that the drinks are distinct.

[edit]

Formal Definitions

Let (P,V) be an interactive proof system where the interactive machines P and V model the prover and verifier. (P,V) is said to be a zero knowledge protocol for proof of membership in a language L if it satisfies the following conditions:

  1. Completeness: For all x\in L, the honest prover P will convince the honest verifier V to accept, except possibly with negligible probability.
  2. Soundness: For all x\not\in L, any cheating prover P * will be unable to convince the honest verifier to accept, except with negligible probability (known as the soundness error). Depending on the class of cheating provers for which this guarantee is made, we have different notions of soundness. (See below.)
  3. Zero Knowledge: For all x\in L, for every PPT interactive machine V * there exists a PPT algorithm S (called the simulator), such that for every x \in L the following two random variables are indistinguishable to a distinguisher or environment. Depending on the class of environments against whom these random variables remain indistinguishable, we have different notions of zero-knowledge. (See below.)
    • \langle P,V^* \rangle (x) (i.e., the output of the interactive machine V * after interacting with P on common input x)
    • S(x)\; (ie the output of the machine S on input x).

The soundness and zero-knowledge property come in different flavors, depending on the class of cheating provers and the class of environments considered.

  • Unconditional soundness: This requires soundness against all (computationally unbounded) cheating provers. This is the standard notion of soundness for a zero-knowledge proof (and for an interactive proof, in general). A stronger notion of soundness, called perfect soundness requires the soundness error to be zero (rather than just negligible).
  • Computational soundness: This requires soundness against all PPT cheating provers. In cryptographic applications, often this level of soundness is sufficient. A protocol with such a soundness guarantee is termed a zero-knowledge argument (rather than a zero-knowledge proof).

Similarly for the zero-knowledge property different classes of environments can be considered:

  • Statistical zero knowledge: This requires indistinguishability of the simulation against all (computationally unbounded) environments. Equivalently, the statistical difference between the distribution of \langle P,V^* \rangle (x) and of S(x)\; is required to be negligible (as a function of the security parameter). A stronger flavor of statistical zero-knowledge, called perfect zero-knowledge requires this statistical difference to be zero.
  • Computational zero knowledge: This requires the indistinguishability of the simulation only against all PPT environments. That is, the distributions of \langle P,V^* \rangle (x) and S(x)\; should be computationally indistinguishable.

Note that in all cases the class of cheating verifiers (as well as the honest verifier) is PPT.

For typical cryptographic applications of zero-knowledge proofs, the proof is a proof of membership in an NP language L, and the prover P is required to be PPT given a witness of membership as input. Also, typically, the applications require some variant of the basic notion defined here. (See below.)

[edit]

Variants and Related Concepts

[edit]

Related Primitives

There are several powerful cryptographic primitives which are closely related to the notion of zero-knowledge proofs. These include Zero-Knowledge proofs of knowledge, Commit-and-Prove protocols, witness indistinguishable proofs (and proofs of knowledge), and non-interactive zero-knowledge proofs (and proofs of knowledge).

[edit]

Composability of Zero-Knowledge Proofs

Composition of protocols refers to preservation of security when independent executions of the protocol are attacked by an adversary. Some of the main facts regarding the sequential, parallel and concurrent execution of zero knowledge protocols

  1. Sequential Composition : Zero Knowledge with respect to auxiliary input is closed under sequential composition
  2. Parallel Composition : In general Zero Knowledge in not closed under parallel composition. Yet, some zero-knowledge proofs preserve their security when man copies are executed in parallel.
  3. Concurrent Composition:


(Main article: Composability of Zero-Knowledge Proofs).

[edit]

Weaker Alternatives to the Zero-Knowledge Property

[edit]
Honest Verifier Zero-Knowledge

A weaker notion of the zero knowledge property requires it to hold only against the honest verifier V (rather than against all probabilistic polynomial time interactive machines. Again it can be perfect, statistical or computation and can be defined for both Zero Knowledge Proofs and Zero Knowledge Arguments.

[edit]
Witness Indistinguishability

For any NP-relation R, a proof system for the corresponding NP-set is called witness indistinguishable if no feasible verifier may distinguish the case in which the proves uses one NP-witness to x to the case in which the prover is using a different NP-witness to the same input x. Clearly any zero knowledge proof is witness indistinguishable, but the converse does not necessarily hold.

[edit]

Relative Complexities of the Cheating Verifier and the Simulator

[edit]
Strict Versus Probabilistic Polynomial time

Probabilistic Polynomial Time(PPT) can also have two interpretations

  • Strict probabilistic polynomial-time: The running time of the machine is polynomially bounded in the security parameter, regardless of its inputs and the outcome of its coin-tosses.
  • Expected probabilistic polynomial-time: For any possible inputs, the expectation (over the coin-tosses) of the random variable representing the running-time is polynomially bounded in the security parameter.
[edit]
Super-polynomial Simulation
[edit]

Zero-Knowledge Proofs for NP Languages

(Main article: Zero-Knowledge Proofs for NP Languages).

[edit]

Zero-Knowledge Proofs for Specific Languages

[edit]

Complexity of Zero-Knowledge Proofs

(Main article: Complexity of Zero-Knowledge Proofs).

[edit]

Applications

[edit]

See Also

Constructions and Lower Bounds for zero knowledge proofs

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Zero-knowledge_proof"
Personal tools