10/11/2017 ZKProofs

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.)

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html 1/4
10/11/2017 ZKProofs

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

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html 2/4
10/11/2017 ZKProofs

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.

One Time Set-up:

1. A trusted center publishes a modulus n = p q that is the product of two primes.
2. Each potential claimant (prover) selects a secret s coprime to n and publishes s = v2 mod n as its
public key.
Protocol: The following is repeated t times.
1. The prover chooses a random r and sends (the witness) r2 mod n to the verifier.
2. The verifier randomly selects a single bit e = 0 or e = 1, and sends e to the prover.
3. The prover computes the response y = r se mod n and sends it to the verifier.
4. The verifier rejects the proof if y = 0 and accepts if y2 = r2v e mod 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.

One Time Set-up:

1. A trusted authority T selects two random primes p and q and forms a modulus n = p q.
2. T defines a public exponent v > 4 with gcd(v, (p-1)(q -1) = 1 so that T can compute s = v-1 mod
(p-1) (q-1).
3. T publishes parameters n and v.
Selection of per-user parameters:
1. Each entity A has a unique identification Id(A). Everyone can calculate a value J(A) = f(Id(A))
mod n (the redundant identity).
2. T gives to each entity A the secret data secret(A) = J(A)-s, which it can calculate.
Protocol: A proves her identity to B using t rounds, each of which consists of:
1. A selects a random secret r and sends her identity Id(A) and x = rv mod n to B.
2. B selects a random challenge e in {1, 2, ... , v}.
3. A computes and sends the following response to B: y = r secret(A)e mod n.
4. B receives y, constructs J(A) = f(Id(A)) mod n, computes z = J(A)eyv, and accepts this round if z
= x mod n.

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html 3/4
10/11/2017 ZKProofs

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 COEN COEN350 T. Schwarz
SCU

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html 4/4