Draft. Aimed at Buhler-Stevenhagen MSRI conference proceedings.

PROTECTING COMMUNICATIONS AGAINST FORGERY

DANIEL J. BERNSTEIN

Abstract. This paper is an introduction to cryptography. It covers secretkey message authentication codes, unpredictable random functions, public-key secret-sharing systems, and public-key signature systems.

1. Introduction

Cryptography protects communications against espionage: an eavesdropper who intercepts a message will be unable to decipher it. This is useful for many types of information: credit-card transactions, medical records, love letters.

There is another side to cryptography. Cryptography protects communications against sabotage: a forger who fabricates or modifies a message will be unable to fool the receiver. This is useful for all types of information. If the receiver does not care about the authenticity of a message, why is he listening to the message in the first place?

This paper explains how cryptography prevents forgery. Section 2 explains how to protect n messages if the sender and receiver share 128(n+1) secret bits. Section 3 explains how the sender and receiver can generate many shared secret bits from a short shared secret. Section 4 explains how the sender and receiver can generate a short shared secret from a public conversation. Section 5 explains how the sender can protect a message sent to many receivers, without sharing any secrets.

2. Unbreakable secret-key authenticators

Here is a protocol for transmitting a message when the sender and receiver both know certain secrets:

Secrets p, k

[figure]

Secrets p, k

[figure]

Message m [figure] Authenticated message m, a [figure] Possibly forged message m′, a′ [figure] Verification

The message is a polynomial m ∈ F [x] with m(0) = 0 and deg m ≤ 1000000. Here F is the field (Z/2)[y]/(y^{128} + y^{9} + y^{7} + y^{2} + 1) of size 2^{128}. The secrets are two independent uniform random elements p, k of F.

The sender transmits (m, a) where a = m(p) + k. The forger replaces (m, a) with (m′, a′); if the forger is inactive then (m′, a′) = (m, a). The receiver discards (m′, a′) unless a′ = m′(p) + k.

The extra information a is called an authenticator.

Date: 2003.09.25. Permanent ID of this document: 9774ae5a1749a7b256cc923a7ef9d4dc.

2000 Mathematics Subject Classification. Primary 94A62.

Security. I claim that the forger has chance smaller than 2^{−108} of fooling the receiver, i.e., of finding (m′, a′) with m′ ≠ m and a′ = m′(p) + k. The proof is easy. Fix (m, a) and (m′, a′), and count pairs (p, k):

• There are exactly 2^{128} pairs (p, k) satisfying a = m(p) + k. Indeed, there is exactly one possible k for each possible p.

• Fewer than 2^{20} of these pairs also satisfy a′ = m′(p) + k, if m′ is different from m. Indeed, any qualifying p would have to be a root of the nonzero polynomial m − m′ − a + a′; this polynomial has degree at most 1000000, so it has at most 1000000 < 2^{20} roots.

Thus the conditional probability that a′ = m′(p) + k, given that a = m(p) + k, is smaller than 2^{20}/2^{128} = 2^{−108}.

In practice, the receiver will continue listening for messages after discarding a forgery, so the forger can try again and again. Consider a persistent, wealthy, longlived forger who tries nearly 2^{75} forgeries by flooding the receiver with one billion messages per second for one million years. His chance of success—his chance of producing at least one (m′, a′) with a′ = m′(p) + k and with m′ not transmitted by the sender—is still smaller than 2^{−108}2^{75} = 2^{−33}.

Handling many messages. One can use a single p with many k’s to protect a series of messages:

\begin{matrix}Secrets \\ p, k_{1}, k_{2}, … \end{matrix}

[figure]

\begin{matrix}Secrets \\ p, k_{1}, k_{2}, … \end{matrix}

[figure]

Message m, ; number n [figure] Authenticated message n, m, a [figure] Possibly forged message n′, m′, a′ [figure] Verification

The sender and receiver share secrets p, k_{1}, k_{2}, k_{3}, …; as above, (p, k_{1}, k_{2}, k_{3}, …) is a uniform random sequence of elements of F. The sender transmits the nth message m as (n, m, a) where a = m(p) + k_{n}. The receiver discards (n′, m′, a′) unless a′ = m′(p) + k_{n′}.

In this context n is called a nonce and a is again called an authenticator. The random function (n, m) ↦ m(p) + k_{n} is called a message authentication code (MAC).

The forger’s chance of success—his chance of producing at least one (n′, m′, a′) with a′ = m′(p) + k_{n′} and with m′ different from any message transmitted by the sender—is smaller than 2^{−108}D, where D is the number of forgery attempts. This is true even if the forger sees all the messages transmitted by the sender. It is true even if the forger can influence the choice of those messages, perhaps responding dynamically to previous authenticators. In fact, is is true even if the forger has complete control over each message!

Define an attack as an algorithm that chooses a message m_{1}, sees the sender’s authenticator m_{1}(p) + k_{1}, chooses a message m_{2}, sees the sender’s authenticator m_{2}(p) + k_{2}, etc., and finally chooses (n′, m′, a′). Define the attack as successful if a′ = m′(p) + k_{n′} and m′ ∉ {m_{1}, m_{2}, … }. Then the attack is successful with probability smaller than 2^{−108}. The proof is, as above, a simple matter of counting.

Of course, if the forger actually has the power to choose a message m_{1} for the sender to authenticate, then the forger does not need to modify messages in transit.

Real senders restrict the messages m_{1}, m_{2}, … that they sign, and thus restrict the possible set of attacks. But the security guarantee does not rely on any such restrictions.

History. Gilbert, MacWilliams, and Sloane in [16, section 9] introduced the first easy-to-compute unbreakable authenticator, using a long shared secret for a long message. Wegman and Carter in [32, section 3] proposed the form h(m) + k_{n} for an authenticator and pointed out that a short secret could handle a long message.

There is now a huge literature on unbreakable MACs. For surveys see [24] and my paper [6]. For two state-of-the-art systems see [8] and [6].

3. Conjecturally unpredictable random functions

Here is a protocol that is conjectured to protect a series of messages:

Secret s [figure] p, k_{1}, k_{2}, …

[figure]

Secret s [figure] p, k_{1}, k_{2}, …

[figure]

Message m, ; number n [figure] Authenticated message n, m, a [figure] Possibly forged message n′, m′, a′ [figure] Verification

The sender and receiver share a secret uniform random 128-bit string s. The sender and receiver compute p = MD5(0, s), k_{1} = MD5(1, s), k_{2} = MD5(2, s), etc. The sender transmits the nth message m as (n, m, a) where a = m(p)+k_{n}. The receiver discards (n′, m′, a′) unless a′ = m′(p) + k_{n′}.

MD5 is the function defined in [27], producing 128-bit output. The function feeds the input bits through a fairly long sequence of easily computed operations; the result has no apparent structure aside from its computability. Details of the definition are not repeated here.

Note that the sender and receiver can compute MD5(n, s) when they need it, rather than storing the long string (p, k_{1}, k_{2}, …).

Security. A forger, given several authenticated messages, might try to solve for s. Presumably there is only one choice for s consistent with all the authenticators. However, the fastest known method of solving for s is to search through all 2^{128} possibilities. This is far beyond the computer power available today.

Is there a faster attack? Perhaps. We believe that this protocol is unbreakable, but we have no proof. (The random string (p, k_{1}, k_{2}, …) is not uniform, so the proof in Section 2 does not apply.) On the other hand, this protocol has the advantage of using only 128 shared secret bits to handle any number of messages.

Unpredictability. Let u be a uniform random function from {0, 1, 2, … } to F. Consider oracle algorithms A that print 0 or 1. What is the difference between

• the probability that A prints 1 using n ↦ MD5(n, s) as an oracle and

• the probability that A prints 1 using u as an oracle? It is conjectured that the difference is smaller than 2^{−40} for every A that finishes in at most 2^{80} steps. In short, n ↦ MD5(n, s) is conjectured to be unpredictable.

If n ↦ MD5(n, s) is, in fact, unpredictable, then this authentication protocol is unbreakable: a fast algorithm that makes D forgery attempts cannot succeed with probability larger than 2^{−105}D + 2^{−40}.

History. Turing introduced the concept of unpredictability in [31]: “Suppose we could be sure of finding [laws of behaviour] if they existed. Then given a discretestate machine it should certainly be possible to discover by observation sufficient about it to predict its future behaviour, and this within a reasonable time, say a thousand years. But this does not seem to be the case. I have set up on the Manchester computer a small programme using only 1000 units of storage, whereby the machine supplied with one sixteen figure number replies with another within two seconds. I would defy anyone to learn from these replies sufficient about the programme to be able to predict any replies to untried values.”

The literature is full of very quickly computable short random functions that seem difficult to predict. Here short means that the random function is determined by a short uniform random string. Unfortunately, most of these random functions are “block ciphers” burdened by the unnecessary constraint of invertibility. See the books [29] and [20] for descriptions of many “block ciphers” and “random-access stream ciphers.”

Blum, Blum, and Shub in [11] constructed a fast short random function with a small input, and proved that any fast algorithm to predict that function could be turned into a surprisingly fast algorithm to factor integers. Naor and Reingold in [23] constructed fast random functions with large inputs and with similar guarantees of unpredictability. These functions are never used in practice, because they are not nearly as fast as MD5; but they show that unpredictability is not a silly concept.

Unpredictability has an interesting application to complexity theory: one can use it to turn fast probabilistic algorithms into reasonably fast deterministic algorithms. This was pointed out by Yao in [36]. It is now widely believed that the complexity classes BPP and P are identical, i.e., that everything decidable in polynomial time with the help of randomness is also decidable in polynomial time deterministically. See [17].

Beware that the name “unpredictable” has several aliases in the literature. See my paper [5, Section 2] for further discussion.

4. Public-key secret sharing

Here is a protocol for the sender and receiver to generate a 128-bit shared secret from a public conversation:

Sender’s ; secret b

[figure]

[figure] Receiver’s ; secret c

[figure]

[figure]

Sender’s public key G(b)

[figure]

[figure]

Receiver’s public key G(c)

[figure]

[figure]

Shared secret s = MD5(−1, G(b), G(bc))

Shared secret s = MD5(−1, G(b), G(bc))

The sender starts from a secret uniform random b ∈ 16Z with 0 ≤ b < 2^{226}. The sender computes and announces a public key G(b). Here G(b) is, by definition, the x-coordinate of the bth multiples of the points (53(2^{224} − 1)/(2^{8} − 1), ± …) on the elliptic curve y^{2} = x^{3} + 7530x^{2} + x over the field Z/(2^{226} − 5). It is not difficult to compute G(b) from b; see [9] and Chapter XXX of this book.

Similarly, the receiver starts from a secret uniform random c ∈ 16Z with 0 ≤ c < 2^{226}. The receiver computes and announces a public key G(c).

The sender and receiver are assumed to receive correct copies of G(b) and G(c) from each other. Subsequent messages are protected against forgery, but the public keys themselves must be protected by something outside this protocol.

The sender now computes G(bc); it is not difficult to compute G(bc) from b and G(c), both of which are known to the sender. The receiver computes G(bc) from c and G(b) in the same way. Finally, the sender and receiver both compute s = MD5(−1, G(b), G(bc)).

As in Section 3, the sender and receiver can use this shared secret s to protect the authenticity of a series of messages:

Sender’s ; secret b

[figure]

[figure] Receiver’s ; secret c

[figure]

[figure]

Sender’s public key G(b)

[figure]

[figure]

Receiver’s public key G(c)

[figure]

[figure]

Shared secret s = MD5(−1, G(b), G(bc))

[figure]

Shared secret s = MD5(−1, G(b), G(bc))

[figure]

p, k_{1}, k_{2}, …

[figure]

p, k_{1}, k_{2}, …

[figure]

Message m, ; number n [figure] Authenticated message n, m, a [figure] Possibly forged message n′, m′, a′ [figure] Verification

The sender can reuse his secret b with other receivers: given the public key G(d) of another receiver, the sender computes MD5(−1, G(b), G(bd)) and continues as above. The sender and receiver can also reverse roles, using MD5(−1, G(c), G(bc)) and MD5(−1, G(d), G(bd)) for messages sent in the opposite direction.

Security. The complete definition of security here is more complicated than it was in Sections 2 and 3, because the forger has more power. In particular, the forger is given the public keys. The forger can also feed a number G(c) to the sender (without necessarily knowing what c is) and receive authenticators computed using MD5(−1, G(b), G(bc)).

The fastest known attack is to start from the public key G(b), perform about 2^{112} elliptic-curve operations, and deduce the secret b, after which the forger can compute s = MD5(−1, G(b), G(bc)) in the same way as the sender. As in Section 3, this is beyond the computer power available today, but there may be faster attacks.

Note that this attack does not depend on the details of MD5. More precisely, consider a generic protocol in which the sender and receiver use an oracle for any 128-bit function in place of MD5; then there is a generic attack in which the forger, having access to the same oracle, succeeds in forgeries after about 2^{112} elliptic-curve operations.

Any generic attack that succeeds for all 128-bit functions—or, more generally, succeeds with probability ϵ on average over all 128-bit functions—can be converted into an algorithm at comparable speed that, given G(b) and G(c), computes G(bc) with probability comparable to ϵ. The idea of the proof is that if the algorithm never feeds G(bc) to the oracle then it has no information about the shared secret. Of course, the value of this proof is limited, for two reasons: first, there might be faster non-generic attacks that exploit the structure of MD5; second, we have no proof that computing G(bc) from G(b) and G(c) is difficult.

History. Diffie and Hellman in [12] introduced the general idea of sharing a secret through a public channel. They also introduced the specific approach of exchanging public keys 2^{b} mod ℓ and 2^{c} mod ℓ to share a secret 2^{bc} mod ℓ; here ℓ is a fixed prime. The problem of computing 2^{bc} mod ℓ from 2^{b} mod ℓ and 2^{c} mod ℓ is called the Diffie-Hellman problem.

There are surprisingly fast techniques to compute b from 2^{b} mod ℓ. See Chapter XXX of this book. Consequently one must choose a rather large prime ℓ in the Diffie-Hellman system.

Miller in [21], and independently Koblitz in [18], suggested replacing the unit group (Z/ℓ)^{∗} with an elliptic curve over Z/ℓ. No surprisingly fast techniques are known for the “elliptic-curve Diffie-Hellman problem” for most curves with nearprime order, so we believe that a relatively small value of ℓ, such as ℓ = 2^{226} − 5, is safe. My elliptic curve y^{2} = x^{3} + 7530x^{2} + x over the field Z/(2^{226} − 5) has order (2^{226} − 5) + 1 − 12000403261375786655687951397247436, which is 16 times a prime.

Elliptic-curve computations involve more effort than unit-group operations, but the smaller size of ℓ makes the Miller-Koblitz elliptic-curve variant faster than the original Diffie-Hellman system. It also means that the keys are shorter. The variant is becoming increasingly popular.

Fiat and Shamir in [15] proved that a generic attack on one protocol could be converted into an algorithm to solve an easy-to-state mathematical problem. Bellare and Rogaway in [4] expanded the idea to more protocols. Many such proofs have now been published.

5. Public-key signatures

Here is a protocol, without any shared secrets, for the sender to protect messages sent to many receivers:

Sender’s ; secret p, q, z

[figure] [figure] Sender’s ; public key pq

[figure]

Message m [figure]

Signed ; message ; m, f, h, r, s, t

[figure] Possibly forged message m′, f′, h′, r′, s′, t′ [figure] Verification

The sender starts from a secret uniform random 256-bit string z, and secret uniform random primes p, q in the interval [2^{768}, 2^{768}+2^{766}] with p mod 8 = 3 and q mod 8 = 7; primality can be tested quickly, as explained in Chapter XXX of this book. The sender computes and announces the product pq, which is assumed to be transmitted correctly to all receivers. Subsequent messages are protected against forgery as follows.

Given a message m, the sender computes • r = MD5(−2, z, m) mod 16;

• h = MD5(−12, r, m)+2^{128} MD5(−13, r, m)+⋯+2^{1408} MD5(−23, r, m)+1;

• u = h^{(q+1)/4} mod q;

• e = 1 if u^{2} ≡ h (mod q), else e = −1;

• v = (eh)^{(p+1)/4} mod p;

• f = 1 if v^{2} ≡ eh (mod p), else f = 2;

• w = f^{(3q−5)/4}u mod q;

• x = f^{(3p−5)/4}v mod p;

• y = w + q(q^{p−2}(x − w) mod p);

• s = min{y, pq − y}; and

• t = (fs^{2} − eh)/pq. The sender then transmits (m, e, f, h, r, s, t).

At this point (e, f, h, r, s, t) is a signature of m under the public key pq. This means, by definition, that e ∈ {1, −1}; f ∈ {1, 2}; r ∈ {0, 1, …, 15}; s and t are integers; h = MD5(−12, r, m)+2^{128} MD5(−13, r, m)+⋯+2^{1408} MD5(−23, r, m)+1; and fs^{2} = tpq + eh.

The receiver discards (m′, e′, f′, h′, r′, s′, t′) if (e′, f′, h′, r′, s′, t′) is not a signature of m′. The receiver can save time here by checking the equation f′(s′)^{2} = t′pq+e′h′ modulo a secret 128-bit prime.

Observe that signatures are different from authenticators: a signature can be verified by anyone, while an authenticator can be verified only by people who could have created the authenticator. The receiver can convince third parties that the sender signed a message; the receiver cannot convince third parties that the sender authenticated a message. Signatures are appropriate for public communications; authenticators are appropriate for private communications.

Security. Like the protocols in Sections 3 and 4, this protocol appears to make forgeries extremely difficult, even if the forger can inspect signatures on messages under his control. There are surprisingly fast techniques to factor pq into p, q—see Chapter XXX of this book—but for large pq these computations are beyond the computer power available today.

One can prove that any generic attack against this protocol can be converted into an algorithm at comparable speed to factor pq with comparable success probability. However, as in Section 4, the value of this proof is limited: there might be faster non-generic attacks, and we have no proof that factorization is difficult.

History. Diffie and Hellman in [12] introduced the idea of public-key signatures. Rivest, Shamir, and Adleman in [28] are often credited with the first useful example; but the original RSA system is obviously breakable.

(In the original RSA system, s was a signature of m under a public key (n, e) if s^{e} ≡ m (mod n). First obvious attack: the forger immediately computes the message 2^{e} mod n with signature 2. Second obvious attack: starting from m, the forger obtains from the sender a signature on the message 2^{e}m mod n, and then divides the result by 2 modulo n.)

Rabin in [26] introduced the first useful signature system. The system shown above is Rabin’s system with improvements by Williams in [34], Barwood, Wigley, and me. Recent results of Bleichenbacher, Coppersmith, and Elkies show that signatures and public keys can be compressed to a surprising extent.

There are other signature systems, notably the ElGamal system in [14], which uses Diffie-Hellman public keys. Keys and signatures in elliptic-curve variants of ElGamal’s system are much smaller than keys and signatures in Rabin-type systems; on the other hand, signature verification is much slower. Both types of systems are widely used.

References

[1] —, 23rd annual symposium on foundations of computer science, IEEE Computer Society, New York, 1982. MR 85k:68007.

[2] —, 38th annual symposium on foundations of computer science, IEEE Computer Society Press, Los Alamitos, 1997. ISBN 0–8186–8197–7.

[3] Victoria Ashby (editor), First ACM conference on computer and communications security, Association for Computing Machinery, New York, 1993.

[4] Mihir Bellare, Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in [3] (1993), 62–73.

[5] Daniel J. Bernstein, How to stretch random functions: the security of protected counter sums, Journal of Cryptology 12 (1999), 185–192. ISSN 0933–2790. Available from http://cr.yp.

to/papers.html.

[6] Daniel J. Bernstein, Floating-point arithmetic and message authentication. Available from

http://cr.yp.to/papers.html.

[7] Daniel J. Bernstein, A secure public-key signature system with extremely fast verification.

Available from http://cr.yp.to/papers.html.

[8] John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, Phillip Rogaway, UMAC: fast and secure message authentication, in [33] (1999), 216–233. Available from http://www.cs.

ucdavis.edu/~rogaway/umac/.

[9] Ian F. Blake, Gadiel Seroussi, Nigel P. Smart, Elliptic curves in cryptography, Cambridge University Press, Cambridge, 2000. ISBN 0–521–65374–6. MR 1 771 549.

[10] G. R. Blakley, David Chaum (editors), Advances in cryptology: CRYPTO ’84, Lecture Notes in Computer Science, 196, Springer-Verlag, Berlin, 1985. ISBN 3–540–15658–5. MR 86j:94003.

[11] Lenore Blum, Manuel Blum, Michael Shub, A simple unpredictable pseudo-random number generator, SIAM Journal on Computing 15 (1986), 364–383. ISSN 0097–5397. MR 87k:65007.

Available from http://cr.yp.to/bib/entries.html#1986/blum.

[12] Whitfield Diffie, Martin Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (1976), 644–654. ISSN 0018–9448. MR 55:10141.

[13] Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in [10] (1985), 10–18; see also newer version in [14]. MR 87b:94037.

[14] Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31 (1985), 469–472; see also older version in [13]. ISSN 0018–9448. MR 86j:94045.

[15] Amos Fiat, Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, in [25] (1987), 186–194. MR 88m:94023.

[16] Edgar N. Gilbert, F. Jessie MacWilliams, Neil J. A. Sloane, Codes which detect deception, Bell System Technical Journal 53 (1974), 405–424. ISSN 0005–8580. MR 55:5306.

[17] Oded Goldreich, Modern cryptography, probabilistic proofs and pseudorandomness, Springer-Verlag, Berlin, 1999. ISBN 3–540–64766–X. MR 2000f:94029.

[18] Neal Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48 (1987), 203–209. ISSN 0025–5718. MR 88b:94017.

[19] Hugo Krawczyk (editor), Advances in cryptology: CRYPTO ’98, Lecture Notes in Computer Science, 1462, Springer-Verlag, Berlin, 1998. ISBN 3–540–64892–5. MR 99i:94059.

[20] Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of applied cryptography, CRC Press, Boca Raton, Florida, 1996. ISBN 0–8493–8523–7. MR 99g:94015. Available

from http://cacr.math.uwaterloo.ca/hac.

[21] Victor S. Miller, Use of elliptic curves in cryptography, in [35] (1986), 417–426. MR 88b:68040.

[22] Gary L. Mullen, Peter Jau-Shyong Shiue (editors), Finite fields: theory, applications, and algorithms, American Mathematical Society, Providence, 1994. ISBN 0–8218–5183–7. MR 95c:11002.

[23] Moni Naor, Omer Reingold, Number-theoretic constructions of efficient pseudo-random functions, in [2] (1997), 458–467. Available from http://www.wisdom.weizmann.ac.il/

~naor/onpub.html.

[24] Wim Nevelsteen, Bart Preneel, Software performance of universal hash functions, in [30] (1999), 24–41.

[25] Andrew M. Odlyzko (editor), Advances in cryptology—CRYPTO ’86: proceedings of the conference on the theory and applications of cryptographic techniques held at the University of California, Santa Barbara, Calif., August 11–15, 1986, Lecture Notes in Computer Science, 263, Springer-Verlag, Berlin, 1987. ISBN 3–540–18047–8. MR 88h:94004.

[26] Michael O. Rabin, Digitalized signatures and public-key functions as intractable as factorization, Technical Report 212, MIT Laboratory for Computer Science, 1979. Available from

http://ncstrl.mit.edu/Dienst/UI/2.0/Describe/ncstrl.mit lcs/MIT/LCS/TR-212.

[27] Ronald L. Rivest, The MD5 message-digest algorithm, Request For Comments 1321 (1992).

Available from http://theory.lcs.mit.edu/~rivest/rfc1321.txt.

[28] Ronald L. Rivest, Adi Shamir, Leonard M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21 (1978), 120–126. ISSN

0001–0782. Available from http://cr.yp.to/bib/entries.html#1978/rivest.

[29] Bruce Schneier, Applied cryptography: protocols, algorithms, and source code in C, 2nd edition, Wiley, New York, 1996. ISBN 0–471–12845–7.

[30] Jacques Stern (editor), Advances in cryptology: EUROCRYPT ’99, Lecture Notes in Computer Science, 1592, Springer-Verlag, Berlin, 1999. ISBN 3–540–65889–0. MR 2000i:94001.

[31] Alan M. Turing, Computing machinery and intelligence, MIND 59 (1950), 433–460. ISSN 0026–4423. MR 12,208c.

[32] Mark N. Wegman, J. Lawrence Carter, New hash functions and their use in authentication and set equality, Journal of Computer and System Sciences 22 (1981), 265–279. ISSN 0022–

0000. MR 82i:68017. Available from http://cr.yp.to/bib/entries.html#1981/wegman.

[33] Michael Wiener (editor), Advances in cryptology—CRYPTO ’99, Lecture Notes in Computer Science, 1666, Springer-Verlag, Berlin, 1999. ISBN 3–5540–66347–9. MR 2000h:94003.

[34] Hugh C. Williams, A modification of the RSA public-key encryption procedure, IEEE Transactions on Information Theory 26 (1980), 726–729. ISSN 0018–9448. Available from http://cr.

yp.to/bib/entries.html#1980/williams.

[35] Hugh C. Williams (editor), Advances in cryptology: CRYPTO ’85, Lecture Notes in Computer Science, 218, Springer, Berlin, 1986. ISBN 3–540–16463–4.

[36] Andrew C. Yao, Theory and applications of trapdoor functions, in [1] (1982), 80–91.

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@cr.yp.to