COEN
350 Zero Knowledge Proofs |

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

- Reciprocity of Identification (unilateral or mutual).
- Costs of Computation.
- Costs of Communication (e.g. number of rounds).
- Existence, Involvement of Third Parties and Trust therein.
- Nature of Security Guarantees.
- 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.

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

**Security:**An impostor can comply with the protocol only with overwhelmingly small probability.**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).**Soundness:**An interactive proof is*sound*if there is an algorithm M with the following properties:- M is polynomial time.
- 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.)

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

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

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.

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

- Claimant (Prover) to Verifier: Witness
- Verifier to Claimant: Challenge
- 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.

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:
- A trusted center publishes a modulus
*n = p · q*that is the product of two primes. - Each potential claimant (prover) selects a secret
*s*coprime to*n*and publishes*s*=*v*^{2}mod*n*as its public key.

- A trusted center publishes a modulus
- Protocol: The following is repeated
*t*times.- The prover chooses a random
*r*and sends (the witness)*r*^{2}mod*n*to the verifier. - The verifier randomly selects a single bit
*e*= 0 or*e*= 1, and sends*e*to the prover. - The prover computes the response
*y*=*r · s*mod^{e}*n*and sends it to the verifier. - The verifier rejects the proof if
*y*= 0 and accepts if*y*^{2}=*r*^{2}*v*^{e }mod*n*.

- The prover chooses a random

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 *a*^{2}/*v*. Upon receiving *e *= 1, he
sends *y* = *a*. Then *y*^{2} = *a*^{2}/*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 *a*^{2}. 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.

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

- One Time Set-up:
- A trusted authority T selects two random primes
*p*and*q*and forms a modulus*n*=*p*·*q*. - 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). - T publishes parameters
*n*and*v.*

- A trusted authority T selects two random primes
- Selection of per-user parameters:
- Each entity A has a unique identification Id(A). Everyone can calculate
a value J(A) =
*f*(Id(A)) mod*n*(the redundant identity). - T gives to each entity A the secret data secret(A) = J(A)
^{-s}, which it can calculate.

- Each entity A has a unique identification Id(A). Everyone can calculate
a value J(A) =
- Protocol: A proves her identity to B using
*t*rounds, each of which consists of:- A selects a random secret
*r*and sends her identity Id(A) and*x*=*r*^{v}mod*n*to B. - B selects a random challenge
*e*in {1, 2, ... ,*v*}. - A computes and sends the following response to B:
*y*=*r*· secret(A)^{e}mod*n.* - B receives
*y*, constructs J(A) =*f*(Id(A)) mod*n*, computes*z*= J(A)^{e}*y*^{v}, and accepts this round if*z*=*x*mod*n.*

- A selects a random secret

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 |