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.