COEN 350
Zero Knowledge Proofs

Introduction

To identify one-self to another entity, an entity can use something known (e.g. passwords), something possessed (a token card), or something inherent (biometric measurements). Identification protocols may be measured by

  1. Reciprocity of Identification (unilateral or mutual).
  2. Costs of Computation.
  3. Costs of Communication (e.g. number of rounds).
  4. Existence, Involvement of Third Parties and Trust therein.
  5. Nature of Security Guarantees.
  6. Storage of Secrets.

In a challenge response scheme, the claimant proves its identity to the verifier by demonstrating knowledge of a secret associated with the claimant. This can be done for example by using a scheme that generates sequence numbers in a way that is unpredictable to someone not privy to the scheme, in this example the secret is the knowledge of how to generate the sequence numbers. It can also be done by using a challenge-response scheme based on symmetric or asymmetric key encryption. For example, the verifier sends a random number, and the claimant returns the random number encrypted.

A disadvantage of password protocols is that if A gives its password to B, then B can impersonate A. Challenge-response schemes improve on this because A only proves knowledge of a secret, but does not give out the secret. However, in the execution of the protocol, A gives hints to B (and any eavesdropper). Zero knowledge proofs are designed to let a claimant demonstrate the knowledge of the secret without revealing any information whatsoever about the secret. More generally, a zero knowledge protocol allows a proof of the truth of an assertion without conveying no information whatsoever about the assertion itself rather than its actual truth.

Definition

A zero-knowledge protocol are instances of an interactive proof system, where claimant and verifier exchange messages (typically depending on random events).

  1. Security: An impostor can comply with the protocol only with overwhelmingly small probability.
  2. Completeness: An interactive proof is complete if the protocol succeeds (for a honest proofer and a honest verifier) with overwhelming probability p > 1/2. (Typically, p ~ 1).
  3. Soundness: An interactive proof is sound if there is an algorithm M with the following properties:
    1. M is polynomial time.
    2. If a dishonest prover can with non-negligible probability successfully execute the protocol with the verifier, then M can be used to extract knowledge from this prover which with overwhelming probability allows successful subsequent protocol executions. (In effect, if someone can fake the scheme, then so can everyone observing the protocol e.g. by computing the secret of the true proover.)
  4. Zero-Knowledge (ZK) Property: There exists a simulator (an algorithm) that can simulate (upon input of the assertion to be proven, but without interacting with the real prover) an execution of the protocol that for an outside observer cannot be distinguished form an execution of the protocol with the real prover.

Example

Quisquater and Guillou (Crypto 89) explain zero-knowledge proofs with the following example:

Alice wants to convince Bob that she knows the secret to pass through the door between points C and D. Bob lets Alice go into the cave to either point C or D. When Alice got there, she cries to Bob to come to point B. Bob has no way to know whether Alice is at C or D. Bob now cries out "left" or "right", and if Alice knows the secret passway she can follow his command. They then walk out of the cave. Alice and Bob then repeats the procedure n times. If Alice knows the secret, then she always passes Bob's test (completeness). If she does not, then she can comply with Bob's request only with probability 2-n (proof). If an impostor can fool Bob, then there must be an alternative way from C to D and anybody can use it (soundness). If Bob videotapes his interactions with Alice, then there is no way to distinguish it from a staged version of the protocol (where Bob and Alice script challenge and response in advance).

NP-Hard Problems

We can use many computationally hard problems for zero-knowledge proofs. One such problem is the one of determining whether two graphs are isomorphic. Assume that Alice's secret is an isomorphism between two graphs G and H. An isomorphism between two graphs is a bjection f between the vertices of the graphs so that (f(x),f(y)) is an edge if and only if (x,y) is an edge. There is no known fast algorithm to decide whether two graphs are isomorphic.

Assume Alice wants to prove to Bob that she is herself by demonstrating that she knows the isomorphism between G and H. She permutes the vertices of G in order to generate a graph K that is isomorphic to G and H and sends it to Bob. Bob challenges her by asking her to either proof that K and G are isomorphic or that K and H are isomorphic. Alice complies. The whole process (generation of a new K, showing either that K is isomorphic to G or that K is isomorphic to H depending on Bob's choice) is repeated n times.

Three Stage ZK protocols

A large class of zero-knowledge protocols consists in repeating n times the following three message rounds:

  1. Claimant (Prover) to Verifier: Witness
  2. Verifier to Claimant: Challenge
  3. Claimant to Verifier: Response

The prover selects a random element from a pre-defined set as its secret commitment and from this computes a public witness. The randomness creates unrepeatable execution histories. The claimant basically asserts that it can answer a number of questions. The verifier probabilistically tests this by asking one of these questions. If the claimant is the one it claims to be, then it can answer all questions successfully. The answer to any one of these questions does not provide information about the secret commitment. The Verifier checks the answer for accuracy. The protocol is repeated n times.

Fiat-Shamir Identification

The Fiat Shamir protocol is based on the difficulty of calculating a square-root. The claimant proves knowledge of a square root modulo a large modulus n.

Informally, the challenge (or exam) e selects between two answers: the secret r (to keep the claimant honest) or one that can only be known from s. If a false claimant were to know that the challenge is e = 1, then he could provide an arbitrary number a and send witness a2/v. Upon receiving e = 1, he sends y = a. Then y2 = a2/v · v. If the false claimant were to know that the challenge is e = 0, then he could select an arbitrary number a and send witness a2. This property allows us to simulate runs of the protocol that an outside observer cannot distinguish from real runs (where the challenges e are true random challenges).

Versions of Fiat-Shamir can be used that require little computation and are therefore suitable to identification with low power processors such as those on a token card.

Guillou Quisquater Protocol

The GQ protocol is an extension of the Fiat Shamir protocol that limits the number t of rounds required.

In this protocol, v determines the security level. In Fiat Shamir, v = 2 and there are many rounds. A fraudulent claimant can defeat the protocol by correctly guessing the challenge e (with a 1 in v chance.) GQ seems secure, because we need to extract v-roots modulo n.

©2003 Thomas Schwarz, S.J., COEN, SCU SCU COEN COEN350 T. Schwarz