Prev. Page
Prev. Chapter Home Next Page Next Chapter




CHAPTER 2 1 .............................................. 502
Identification Schemes ............................ 502
Feige-Fiat-Shamir .................................... 502
Simplified Feige-Fiat-Shamir Identificati ....... 502
Feige-Fia t-Shamir Identification Scheme ... 503
An Example ................................................. 504
Enhancements ............................................. 505
Fiat-Shamir Signature Scheme ................... 506
lmproued Fiat-Shamir Signa twre ................. 507
Other Enhancements ................................... 507
Ohta-Okamoto identification Scheme .......... 507
Patents ........................................................ 507
GUILLOU-QUISQUATER ........................ 507
Guillou-Quisquater ldentification Scheme ... 508
Guillou-Quisquater Signature Scheme ........ 508
Multiple Signatures ...................................... 509
SCHNORR ............................................... 509
Authentication Protocol ................................ 510
Digital Signature Protocol ............................ 510
Patents ........................................................ 511
CONVERTING IDENTIFICATION ........... 511
Page 502
Prev. Page
Prev. Chapter Home Next Page Next Chapter




21
CHAPTER


Identification Schemes


2 1.1 FEIGE-FIAT-SHAMIR
Amos Fiat™s and Adi Shamir™s authentication and digital signature scheme is dis-
cussed in [566,567]. Uriel Feige, Fiat, and Shamir modified the algorithm to a zero-
knowledge proof of identity [.544,545]. This is the best-known zero-knowledge proof
of identity.
On July 9, 1986 the three authors submitted a U.S. patent application [1427].
Because of its potential military applications, the application was reviewed by the
military. Occasionally the Patent Office responds not with a patent, but with some-
thing called a secrecy order. On January 6, 1987, three days before the end of their
six-month period, the Patent Office imposed that order at the request of the Army.
They stated that “. . . the disclosure or publication of the subject matter . . . would
be detrimental to the national security. . . .” The authors were ordered to notify all
Americans to whom the research had been disclosed that unauthorized disclosure
could lead to two years™ imprisonment, a $10,000 fine, or both. Furthermore, the
authors had to inform the Commissioner of Patents and Trademarks of all foreign
citizens to whom the information had been disclosed.
This was ludicrous. All through the second half of 1986, the authors had pre-
sented the work at conferences throughout Israel, Europe, and the United States.
The authors weren™t even American citizens, and all the work had been done at the
Weizmann Institute in Israel.
Word spread through the academic community and the press. Within two days the
secrecy order was rescinded; Shamir and others believe that the NSA pulled strings
to rescind the order, although they officially had no comment. Further details of this
bizarre story are in [936].
Simplified Feige-Fiat-Shamir Identification Scheme
Before issuing any private keys, the arbitrator chooses a random modulus, n,
which is the product of two large primes. In real life, n should be at least 512 bits
Page 503
Prev. Page
Prev. Chapter Home Next Page Next Chapter
21 Identification Schemes
CHAPTER



long and probably closer to 1024 bits. This n can be shared among a group of
provers. (Choosing a Blum integer makes computation easier, but it is not required
for security.)
To generate Peggy™s public and private keys, a trusted arbitrator chooses a num-
ber, v, where v is a quadratic residue mod n. In other words, choose v such that x2 =
v (mod n) has a solution and v-l mod n exists. This v is Peggy™s public key. Then cal-
culate the smallest s for which s = sqrt (v-l) (mod n). This is Peggy™s private key.
The identification protocol can now proceed.

(1) Peggy picks a random r, where r is less then n. She then computes x =
r2 mod n, and sends x to Victor.
(2) Victor sends Peggy a random bit, b.
(3) If b = 0, then Peggy sends Victor r. If b = 1, then Peggy sends Victory = r sl


mod n.
(4) If b = 0, Victor verifies that x = r2 mod n, proving that Peggy knows sqrt
(x). If b = 1, Victor verifies that x= y2 * v mod n, proving that Peggy knows
sqrt (v-l).

This is a single round-called an accreditation-of the protocol. Peggy and Victor
repeat this protocol t times, until Victor is convinced that Peggy knows s. It™s a cut-
and-choose protocol. If Peggy doesn™t know s, she can pick r such that she can fool
Victor if he sends her a 0, or she can pick r such that she can fool Victor if he sends
her a 1. She can™t do both. The odds of her fooling Victor once are 50 percent. The
odds of her fooling him t times are 1 in 2t.
Another way for Victor to attack the protocol would be trying to impersonate
Peggy. He could initiate the protocol with another verifier, Valerie. In step (l),
instead of choosing a random r, he would just reuse an old r that he saw Peggy use.
However, the odds of Valerie choosing the same value for b in step (2) that Victor did
in the protocol with Peggy are 1 in 2. So, the odds of his fooling Valerie are 50 per-
cent. The odds of his fooling her t times are 1 in 2™.
For this to work, Peggy must not reuse an r, ever. If she did, and Victor sent Peggy
the other random bit in step (2), then he would have both of Peggy™s responses. Then,
from even one of these, he can calculate s and it™s all over for Peggy.
Feige-Fia t-Shamir Identification Scheme
In their papers [544,545], Feige, Fiat and Shamir show how parallel construction
can increase the number of accreditations per round and reduce Peggy and Victor™s
interactions.
First generate n as in the previous example, the product of two large primes. To
generate Peggy™s public and private keys, first choose k different numbers: vl,
v2, . * . 9vk, where each vi is a quadratic residue mod n. In other words, choose v, such
that x2 = Vi mod n has a solution and vi-™ mod n exists. This string, vlr v2, . . . , vk>is
the public key. Then calculate the smallest si such that si = sqrt (vi-˜) mod n. This
string, sl, s2, . . . , Sk,is the private key.
Page 504
Prev. Chapter Prev. Page Home Next Page Next Chapter
21.1 Feige-Fiat-Shamir


And the protocol is:

( 1) Peggy picks a random r, when r is less than n. She then computes x = r2 mod
n, and sends x to Victor.
(2) Victor sends Peggy a random binary string k-bits long: bl, bz, . . . , bk.
(3) Peggy computes y = r (slbl sZb2 . . . Skbk) mod n. (She multiplies
l l l l


together whichever values of si that correspond to bj = 1. If Victor™s first bit
is a 1, then s1 is part of the product; if Victor™s first bit is a 0, then s1 is not
part of the product, and so on.) She sends y to Victor.
(4) Victor verifies that x = y” (vlbr * vZb2 . . . * vkbk) mod n. (He multiplies
l l


together the values of vi based on the random binary string. If his first bit
is a 1, then v1 is part of the product; if his first bit is a 0, then v1 is not part
of the product, and so on.)

Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy
knows S1, S2, . . . , Sk.
The chance that Peggy can fool Victor is 1 in 2kf. The authors recommend a 1 in
220chance of a cheater fooling Victor and suggest that k = 5 and t = 4. If you are more
paranoid, increase these numbers.

An Example
Let™s look at this protocol in action with small numbers.
If n = 35 (the two primes are 5 and 7), then the possible quadratic residues are:
1: x2 = 1 (mod 35) has the solutions: x = 1, 6, 29, or 34.
4: x2 = 4 (mod 35) has the solutions: x = 2, 12, 23, or 33.
9: x2 = 9 (mod 35) has the solutions: x = 3, 17, 18, or 32.
11: x2 = 11 (mod 35) has the solutions: x = 9, 16, 19, or 26.
14: x2 = 14 (mod 35) has the solutions: x = 7 or 28.
15: x2 = 15 (mod 35) has the solutions: x = 15 or 20.
16: x2 = 16 (mod 35) has the solutions: x = 4, 11, 24, or 31.
21: x2 = 21 (mod 35) has the solutions: x = 14 or 21.
25: x2 = 25 (mod 35) has the solutions: x = 5 or 30.
29: x2 = 29 (mod 35) has the solutions: x = 8, 13, 22 or 27.
30: x2 = 30 (mod 35) has the solutions: x = 10 or 25.
The inverses (mod 35) and their square roots are:
s = sqrt (r+)
V v-1

1 1 1
4 9 3
9 4 2
Page 505
Prev. Page
Prev. Chapter Home Next Page Next Chapter
21 Identification Schemes
CHAPTER



11 16 4
16 11 9
29 29 8
Note that 14, 15, 21, 25, and 30 do not have inverses mod 35, because they are
not relatively prime to 35. This makes sense, because there should be (5 - 1) l


(7 - 1)/4 quadratic residues mod 35 relatively prime to 35: That is gcd(x,35) = 1
(see Section 11.3).
So, Peggy gets the public key consisting of k = 4 values: (4,11,16,29]. The corre-
sponding private key is (3,4,9,8). Here™s one round of the protocol.

(1) Peggy chooses a random r = 16, computes 162 mod 35 = 11, and sends it to
Victor.
(2) Victor sends Peggy a random binary string [ l,l,O, 1).
(3) Peggy computes 16 * ((3™) * (4l) * (9™) * (Sl)) mod 35 = 3 1 and sends it to Victor.
(4) Victorverifies that312 * ((4l) * (11™) (16O)* (29l))mod35= 11.
l




Peggy and Victor repeat the protocol t times, each time with a different random r,
until Victor is satisfied.
With small values like these, there™s no real security. But when n is 5 12 bits long
or more, Victor cannot learn anything about Peggy™s secret key except the fact that
she knows it.
Enhancements
It is possible to embed identification information into the protocol. Assume that
1 is a binary string representing Peggy™s identification: her name, address, social
security number, hat size, preferred brand of soft drink, and other personal informa-
tion. Use a one-way hash function H(x) to compute H(l,j), where j is a small number
concatenated onto I. Find a set of is where H(l,j) is a quadratic residue mod n. These
H(I,j)s become vl, vz, . . . , vk (the is need not be quadratic residues). Peggy™s public
key is now I and the list of is. She sends I and the list of is to Victor before step (1)
of the protocol (or perhaps Victor downloads them from a public bulletin board
someplace), and Victor generates v,, v2, . . . , vk from H(l,j).
Now, after Victor successfully completes the protocol with Peggy, he is assured
that Trent, who knows the factorization of the modulus, has certified the associa-
tion between 1 and Peggy by giving her the square roots of the vi derived from I. (See
Section 5.2 for background information.)
Feige, Fiat, and Shamir include the following implementation remarks [544,545]:
For nonperfect hash functions, it may be advisable to randomize Zby concatenat-
ing it with a long random string, Z?.
This string is chosen by the arbitrator and is
revealed to Victor along with I.
In typical implementations, k should be between 1 and 18. Largervalues of k can
reducethe time and communication complexity by reducing the number of rounds.
Page 506
Prev. Chapter Prev. Page Home Next Page Next Chapter




The value n should be at least 512 bits long. (Of course, there has been consid-
erable progress in factoring since then.)
If each user chooses his own n and publishes it in a public key file, they can dis-
pense with the arbitrator. However, this RSA-like variant makes the scheme con-
siderably less convenient.

Fiat-Shamir Signature Scheme
this identification scheme into a signature scheme is basically a matter
Turning
of turning Victor into a hash function. The primary benefit of the Fiat-Shamir digi-
tal signature scheme over RSA is speed: Fiat-Shamir requires only 1 percent to 4 per-
cent of the modular multiplications of RSA. For this protocol, we™ll bring back Alice
and Bob.
The setup is the same as the identification scheme. Choose n to be the product of
two large primes. Generate the public key, vl, v2, . . . , vk, and the private key, sl,
. . . , Sk,such that Si = sqrt (Vi-˜) mod n.
s2,



Alice picks t random integers between 1 and n: rl, r2, . . . , rt, and computes
(1)
. . . , xt such that X, = ri2 mod n.
Xl, x2,

(2) Alice hashes the concatenation of the message and the string of x,s to gen-
erate a bit stream: H(m, x1, x2, . . . , x,). She uses the first k * t bits of this
string as values of bij, where i goes from 1 to t, and j goes from 1 to k.
(3) Alice computes yl, y2, . . . , yt, where
yi = r, * (slbil s2bi2* . . . Skbik)
mod n
l l



(For each i, she multiplies together the values of the si based on the random
bi, i values. If b,, 1 is a 1, then ˜1 is multiplied; if bj, 1 is a 0, then s1 is not
multiplied.)
(4) Alice sends Bob m, all the bit values of bi, i, and all the values of yi. He
already has Alice™s public key: vl, v2, . . . , vk.
(5) Bob computes zl, z2, . . . , z*, where
mod n
(˜1˜x1 v2bi2 * . . . * Vkbik)
Zi = y12 l l



(Again, Bob multiplies based on the bi, i values.) Also note that zi should be
equal t0 Xi.
(6) Bob verifies that the first k * t bits of H(m, zl, z2, . . . , z,) are the bi, i values
that Alice sent him.

As with the identification scheme, the security of this signature scheme is pro-
portional to 1/2kt. It also depends on the difficulty of factoring n. Fiat and Shamir
pointed out that forging a signature is easier when the complexity of factoring n is
considerably lower than 2kf. And, because of birthday-type attacks (see Section 18.1),
they recommend that k * t be increased from 20 to at least 72. They suggest k = 9
andt=8.
Page 507
Prev. Page
Prev. Chapter Home Next Page Next Chapter
21 Identification Schemes
CHAPTER



lmproued Fiat-Shamir Signa twre Scheme
Silvio Micali and Adi Shamir improved the Fiat-Shamir protocol in [ 10881. They
chose vl, vz, . . . , vk to be the first k prime numbers. So
v1 = 2, v2 = 3, v3 = 5, and so on.
This is the public key.
The private key, sl, s2, . . . , sk is a random square root, determined by
S, = sqrt (vi-˜) mod n
In this version, every person must have a different n. The modification makes it
easier to verify signatures. The time required to generate signatures, and the secu-
rity of those signatures, is unaffected.
Other Enhancements
There is also an N-party identification scheme, based on the Fiat-Shamir algo-
rithm [264]. Two other improvements to the Fiat-Shamir scheme are proposed in
[1218]. Another variant is [1368].
Ohta-Okamoto identification Scheme
This protocol is a modification of the Feige-Fiat-Shamir identification scheme and
gets its security from the difficulty of factoring [ 1198,1199]. The same authors also
wrote a multisignature scheme (see Section 23.1), by which a number of different
people can sequentially sign a message [1200]. This scheme has been proposed for
smart-card implementation [850].
Patents
Fiat-Shamir is patented [1427]. Anyone interested in licensing the algorithm
should contact Yeda Research and Development, The Weizmann Institute of Sci-
ence, Rehovot 76100, Israel.


1.2
2 GUILLOU-QUISQUATER
Feige-Fiat-Shamir was the first practical identity-based protocol. It minimized com-
putation by increasing the number of iterations and accreditations per iteration. For
some implementations, like smart cards, this is less than ideal. Exchanges with the
outside world are time-consuming, and the storage required for each accreditation
can strain the limited resources of the card.
Louis Guillou and Jean-Jacques Quisquater developed a zero-knowledge identifi-
cation algorithm more suited to applications like these [670,1280]. The exchanges
between Peggy and Victor and the parallel accreditations in each exchange are
both kept to an absolute minimum: There is only one exchange of one accredita-
tion for each proof. For the same level of security, the computation required by
Guillou-Quisquater is greater than by Feige-Fiat-Shamir by a factor of three. And
Page 508
Prev. Chapter Prev. Page Home Next Page Next Chapter




like Feige-Fiat-Shamir, this identification algorithm can be converted to a digital
signature algorithm.

Guillou-Quisquater lden tifica tion Scheme
Peggy is a smart card who wants to prove her identity to Victor. Peggy™s identity
consists of a set of credentials: a data string consisting of the card™s name, validity
period, a bank account number, and whatever else the application warrants. This bit
string is called 1. (Actually, the credentials can be a longer string and hashed to a 1
value. This complexity does not modify the protocol in any way.) This is analogous
to the public key. Other public information, shared by all “Peggys” who could use
this application, is an exponent v and a modulus n, where n is the product of two
secret primes. The private key is B, calculated such that JB” = 1 (mod n).
Peggy sends Victor her credentials, 1. Now, she wants to prove to Victor that those
credentials are hers. To do this, she has to convince Victor that she knows B. Here™s
the protocol:

(1) Peggy picks a random integer r, such that r is between 1 and n - 1. She com-
putes T = I” mod n and sends it to Victor.
(2) Victor picks a random integer, d, such that d is between zero and v - 1. He
sends d to Peggy.
(3) Peggy computes D = rBd mod n, and sends it to Victor.
(4) Victor computes 7” = D”Jd mod n. If T = 7” (mod n), then the authentication
succeeds.

The math isn™t that complex:
T = pp = (rB”)“Jd = rvBdvJd rv(\Pjd = r” = T (mod n)
=
since B was constructed to satisfy
JB” = 1 (mod n)

Guillou-Quisquater Signature Scheme
This identification can be converted to a signature scheme, also suited for smart-
card implementation [671,672].
The public and private key setup is the same as before. Here™s the protocol:

(1) Alice picks a random integer r, such that r is between 1 and n - 1. She com-
putes T = r” mod n.
(2) Alice computes d = H(M,T), where M is the message being signed and H(x)
is a one-way hash function. The d produced by the hash function must be
between 0 and v - 1 [ 12801. If the output of the hash function is not within
this range, it must be reduced modulo v.
Page 509
Prev. Page
Prev. Chapter Home Next Page Next Chapter

21 Identification Schemes
CHAPTER



(3) Alice computes D = rBd mod n. The signature consists of the message, M,
the two calculated values, d and D, and her credentials, I. She sends this
signature to Bob.
(4) Bob computes T = D”/” mod n. He then computes d™ = H(M,T). If d = d™,
then Alice must know B and the signature is valid.
Multiple Signatures
What if many people want to sign the same document? The easy solution has each
of them signing separately, but this signature scheme can do better than that. Here
Alice and Bob sign the same document and Carol verifies the signatures, but any
number of people can be involved in the signature process. As before, Alice and Bob
have their own unique 1 and B values: (JAIBA) and (JB, The values n and v are com-
BB).
mon to the system.

(1) Alice picks a random integer, r A, such that rA is between 1 and n - 1. She
computes TA = rAv mod n and sends TA to Bob.
(2) Bob picks a random integer, r B,such that rB is between 1 and n - 1. He com-
putes TB = rBvmod n and sends TB to Alice.
(3) Alice and Bob each compute T = (TAT,) mod n.
(4) Alice and Bob each compute d = H(M,T), where M is the message being
signed and H(x) is a one-way hash function. The d produced by the hash
function must be between 0 and v - 1 [ 12801.If the output of the hash func-
tion is not within this range, it must be reduced modulo v.
(5) Alice computes DA = rABAdmod n and sends DA to Bob.
(6) Bob computes DB = rBBBd mod n and sends DB to Alice.
(7) Alice and Bob each compute D = DADB mod n. The signature consists of the
message, M, the two calculated values, d and D, and both of their creden-
tials: IA and fB.
(8) Carol computes J = JAJB mod n.
(9) Carol computes Y = DvJdmod n. She then computes d™ = H(M,T). If d = d™,
then the multiple signature is valid.

This protocol can be extended to any number of people. For multiple people to
sign, they all multiply their individual Ti values together in step (3) and their indi-
vidual D, values together in step (7). To verify a multiple signature, multiply all the
signers /i values together in step (8). Either all the signatures are valid or there is at
least one invalid signature.


21.3 SCHNORR
Claus Schnorr™s authentication and signature scheme [ 1396,1397] gets its security
from the difficulty of calculating discrete logarithms. To generate a key pair, first
Page 510
Prev. Chapter Prev. Page Home Next Page Next Chapter
21.3 Schnorr


choose two primes, p and q, such that q is a prime factor of p - 1. Then, choose an a
not equal to 1, such that aq = 1 (mod p). All these numbers can be common to a
group of users and can be freely published.
To generate a particular public-key/private-key key pair, choose a random num-
ber less than q. This is the private key, s. Then calculate v = amsmod p. This is the
public key.

Authentication Protocol
(1) Peggy picks a random number, r, less than q, and computes x = a™ mod p.
This is the preprocessing stage and can be done long before Victor is
present.
(2) Peggy sends x to Victor.
(3) Victor sends Peggy a random number, e, between 0 and 2™ - 1. (I™ll discuss t
in a moment.)
(4) Peggy computes y = (r + se) mod q and sends y to Victor.
(5) Victor verifies that x = a?.+ mod p.

The security is based on the parameter t. The difficulty of breaking the algorithm
is about 2t. Schnorr recommended that p be about 512 bits, q be about 140 bits, and
t be 72.

Digital Signature Protocol
Schnorr can also be used as a digital signature protocol on a message, M. The
public-key/private-key key pair is the same, but we™re now adding a one-way hash
function, H(M).

(1) Alice picks a random number, r, less than q, and computes x = aTmod p.
This computation is the preprocessing stage.
(2) Alice concatenates M and x, and hashes the result:
e = H(M,x)
(3) Alice computes y = (r + se) mod q. The signature is e and y; she sends these
to Bob.
(4) Bob computes x™ = a%+ mod p. He then confirms that the concatenation of
M and x™ hashes to e.
e = H(M,x™)
If it does, he accepts the signature as valid.

In his paper, Schnorr cites these novel features of his algorithm:
Most of the computation for signature generation can be completed in a prepro-
cessing stage,independent of the messagebeing signed. Hence, it can be done dur-
Page 511
Prev. Chapter Prev. Page Home Next Page Next Chapter
Identification Schemes
CHAPTER 21



ing idle time and not affect the signature speed. An attack against this prepro-
cessing stage is discussed in [475], but I don™t think it™s practical.
For the same level of security, the length of signatures is less for Schnorr than
for RSA. For example, with a 140-bit q, signatures are only 21%bits long, less
than half the length of RSA signatures. Schnorr™s signatures are also much shorter
than ElGamal signatures.

even fewer bits suitable for a given
Of course, practical considerations may make
scheme: For example, an identification scheme where the cheater must perform an
on-line attack in only a few seconds, versus a signature scheme where the cheater
can calculate for years off-line to come up with a forgery.
A modification of this algorithm, by Ernie Brickell and Kevin McCurley, enhances
its security [265].
Patents
Schnorr is patented in the United States [1398] and in many other countries. In
1993, PKP acquired the worldwide rights to the patent (see Section 25.5). The U.S.
patent expires on February 19, 2008.


2 1.4 CONVERTING IDENTIFICATION SCHEMES TO SIGNATURE
SCHEMES
There is a standard method of converting an identification scheme into a signature
scheme: Replace Victor with a one-way hash function. The message is not hashed
before it is signed; instead the hashing is incorporated into the signing algorithm. In
principle, this can be done with any identification scheme.