Cryptographic Protocols - Codes: The Guide to Secrecy from Ancient to Modern Times - page 202

5.3 Identification

Two things are identical if one can be substituted for the other without af-
fecting the truth.
Gottfried Wilhelm Leibniz ( 1646 - 1716 ) , German Philosopher
— translated from Table de definitions (1704) in L. Coutourat (ed.)
Opuscules et fragments inedits de Leibniz (1903)

In order to describe our first identification scheme, we need to discuss how
the participants interact. For instance, Alice and Bob will interact in such a
waythat Alice is able to “prove” her identityto Bob byconvincing him that
she knows a secret without revealing anything about that secret. This type of
identityauthentication is valuable in such instances as Alice having to convince
a merchant that she is the owner of a credit card without revealing the password
or PIN for that card. This is important since revealing the PIN, for instance,
would allow someone to impersonate Alice. (In the modern day, this has come
to be known as identity theft , where a criminal obtains a person's financial
information and uses it to withdraw funds from bank accounts or uses credit
cards to fraudulentlyacquire goods and services.) In other words, we need
mechanisms for authentication that will not give the authenticator the ability
to impersonate you.
A challenge-response protocol is an interactive proof of knowledge involving
two participants, Alice and Bob, say, where Alice is the prover , and Bob is
the verifier . Alice knows a secret S and must convince Bob of knowledge of
this secret. If she reveals nothing about the secret in so doing, it is called a
zero-knowledge proof of knowledge . However, there are rigorous mathematical
constraints in defining such systems into which we will not delve here. For our
needs, the above and what follows are suKcient. For a mathematical analysis
of the theoryof zero-knowledge concepts, see [169, pages 252-261].
We are readyfor our first protocol introduced in 1987 byFiat and Shamir as
an authentication and digital signature scheme in [87]. Later, it was modified
byFeige, Fiat, and Shamir to an identification protocol (see [79] and [80]). For
ease of presentation, we supplya simplified version and we employTrent to set
the stage for us.

(Simplified) Feige-Fiat-Shamir Identification Protocol
Background Assumptions :
First, Trent chooses an RSA modulus n = pq , where p and q are large primes
of roughlythe same size to be kept secret. Also, a parameter a ∈ N is chosen.

) ∗ .
Then theycompute, respectivel, the least residues t A and t B modulo n where

Next, Alice and Bob, respectively, randomly select secret s A ,s B ∈ ( Z /n Z

s 2 A (mod n ) and t B ≡ s 2 B (mod n ) . t A ≡

Theyregister their secrets s A and s B with Trent, whereas t A and t B do not need
to be kept secret. The goal is for Alice to prove her identity, via demonstration