mod n exists. This string, V1, v2, …, vk, is the public key. Then calculate the smallest Si such that si = sqrt (
) mod n. This string, s1, s2, …, sk, is the private key.Amos Fiat’s and Adi Shamir’s authentication and digital signature scheme is discussed 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 something 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 presented 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].
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 long and probably closer to 1024 bits. This 22 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 number, 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−1 mod n exists. This v is Peggy’s public key. Then calculate the smallest s for which s ≡ sqrt (v−1) (mod n). This is Peggy’s private key.
The identification protocol can now proceed.
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 (1), 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 percent. The odds of his fooling her t times are 1 in 2t.
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.
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: v1, v2, …, Vk, where each vi is a quadratic residue mod n. In other words, choose vi such that x2 = Vi mod n has a solution and mod n exists. This string, V1, v2, …, vk, is the public key. Then calculate the smallest Si such that si = sqrt () mod n. This string, s1, s2, …, sk, is the private key.
And the protocol is:
mod n. (She multiplies together whichever values of si that correspond to bi = 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.
mod n. (He multiplies 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 2kt. The authors recommend a 1 in 220 chance of a cheater fooling Victor and suggest that k = 5 and t = 4. If you are more paranoid, increase these numbers.
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:
The inverses (mod 35) and their square roots are:
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) * (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 corresponding private key is {3,4,9,8}. Here’s one round of the protocol.
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 512 bits long or more, Victor cannot learn anything about Peggy’s secret key except the fact that she knows it.
It is possible to embed identification information into the protocol. Assume that I is a binary string representing Peggy’s identification: her name, address, social security number, hat size, preferred brand of soft drink, and other personal information. Use a one-way hash function H(x) to compute H(I,j), where j is a small number concatenated onto I. Find a set of js where H(I,j) is a quadratic residue mod n. These H(I,j)s become v1, v2, …, vk (the js need not be quadratic residues). Peggy’s public key is now I and the list of js. She sends I and the list of js to Victor before step (1) of the protocol (or perhaps Victor downloads them from a public bulletin board someplace), and Victor generates v1, v2, …, vk from H(I,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 association between I 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 I by concatenating it with a long random string, R. 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. Larger values of k can reduce the time and communication complexity by reducing the number of rounds.
The value n should be at least 512 bits long. (Of course, there has been considerable progress in factoring since then.)
If each user chooses his own n and publishes it in a public key file, they can dispense with the arbitrator. However, this RSA-like variant makes the scheme considerably less convenient.
Turning this identification scheme into a signature scheme is basically a matter of turning Victor into a hash function. The primary benefit of the Fiat-Shamir digital signature scheme over RSA is speed: Fiat-Shamir requires only 1 percent to 4 percent of the modular multiplications of RSA. For this protocol, well 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, v1 v2, …, vk, and the private key, s1, s2, …, sk, such that si = sqrt (
) mod n.
mod n.
(For each i, she multiplies together the values of the sj based on the random bi, j values. If bi, 1 is a 1, then S1 is multiplied; if bi, 1 is a 0, then S1 is not multiplied.)
(Again, Bob multiplies based on the bi, j values.) Also note that zi should be equal to xi.
As with the identification scheme, the security of this signature scheme is proportional 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 2kt. 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 and t = 8.
Silvio Micali and Adi Shamir improved the Fiat-Shamir protocol in [1088]. They chose V1, v2, …, Vk to be the first k prime numbers. So
This is the public key.
The private key, s1, s2, …, sk is a random square root, determined by
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 security of those signatures, is unaffected.
There is also an N-party identification scheme, based on the Fiat-Shamir algorithm [264]. Two other improvements to the Fiat-Shamir scheme are proposed in [1218]. Another variant is [1368].
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].
Fiat-Shamir is patented [1427]. Anyone interested in licensing the algorithm should contact Yeda Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.
Feige-Fiat-Shamir was the first practical identity-based protocol. It minimized computation 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 identification 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 accreditation 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 like Feige-Fiat-Shamir, this identification algorithm can be converted to a digital signature algorithm.
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 J. (Actually, the credentials can be a longer string and hashed to a J 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 JBV ≡ 1 (mod n).
Peggy sends Victor her credentials, J. 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:
The math isn’t that complex:
since B was constructed to satisfy
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:
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 J and B values: (JA, BA) and (JB, BB). The values n and v are common to the system.
mod n and sends TA to Bob.
mod n and sends TB to Alice.
mod n and sends DA to Bob.
mod n and sends DB to Alice.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 individual Di values together in step (7). To verify a multiple signature, multiply all the signers Ji values together in step (8). Either all the signatures are valid or there is at least one invalid signature.
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 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 number less than q. This is the private key, s. Then calculate v = a−s mod p. This is the public key.
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.
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).
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 preprocessing stage, independent of the message being signed. Hence, it can be done during idle time and not affect the signature speed. An attack against this preprocessing 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 212-bits long, less than half the length of RSA signatures. Schnorr’s signatures are also much shorter than ElGamal signatures.
Of course, practical considerations may make even fewer bits suitable for a given 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].
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.
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.