next up previous contents
Next: References Up: 5 Randomness in Computing. Previous: 5.4 Pseudo-randomness.

5.5 Cryptography.

Rabin's One-way Function. Pick random prime numbers p,q,|p|=|q| with 2 last bits =1, i.e. with odd . Then is called a Blum number. Its length should make factoring infeasible.

Let be the set of quadratic residues, i.e. numbers of the form .

Lemma. If n=pq is a Blum number then is a permutation of .

Proof: Let and . Let . It is odd, so is an integer. Since 2t is a multiple of both p-1 and q-1, according to the Little Fermat Theorem divides both p and q (and, thus n). Then . Q.E.D.

Lemma. Inverting F on random x is equivalent to factoring n.

Proof. Let for a fraction of . Then , while for a fraction of x. The Square Root Test would factor n given any such which could be found in about random trials. Conversely, knowing a secret (factors of n) makes inverting F easy; such one-way permutations, called ``trap-door,'' have many applications, such as cryptography (see below).

Picking a prime number is easy since primes have density 1/O(|p|). Indeed, one can see that (2n)!/(n!2) is divisible by every prime p in [n,2n] but by no prime in [2n/3,n] or prime power pi > 2n. So, (log((2n)!/(n!2))) /log n = 2n/log n -O(1) is an upper bound on the number of primes in [n,2n] and a lower bound on that in [1,2n].
Note that fast VLSI circuits exist to multiply large numbers and check primality.

Public Key Encryption.

A perfect way to encrypt a message m is to add it bit by bit to a random string S of the same length k. The resulting encryption has the same uniform probability distribution, no matter what m is. So it is useless for the adversary who wants to learn something about m, without knowing S. A disadvantage is that the communicating parties must share a secret S as large as all messages to be exchanged combined. Public Key Cryptosystems use two keys. One key is needed to encrypt the messages and may be completely disclosed to the public. The decryption key must still be kept secret, but need not be sent to the encrypting party. The same keys may be used repeatedly for many messages.

Such cryptosystem can be obtained [Blum, Goldwasser 1982] by replacing the above random S by pseudorandom ; . Here a Blum number n=pq is chosen by the Decryptor and is public, but p,q are kept secret. The Encryptor chooses at random and sends . Assuming factoring is intractable for the adversary, S should be indistinguishable from random strings (even when is known). Then this scheme is as secure as if S were random. The Decryptor knows p,q and can compute u,t (see above) and . So, he can find , and then S and m.

Another use of the intractability of factoring is digital signatures [Rivest, Shamir, Adleman 1978], [Rabin, 1979]. Strings x can be released as authorizations of . Anyone can verify x, but nobody can forge it since only the legitimate user knows factors of n and can take square roots.

Go On!

You noticed that most of our burning questions are still open. Take them on! Start with reading recent results (FOCS/STOC is a good source). See where you can improve them. Start writing, first notes just for your friends, then the real papers. Here is a little writing advice:

A well written paper has clear components: skeleton, muscles, etc. The skeleton is an acyclic digraph of basic definitions and statements, with cross-references. The meat consists of proofs (muscles) each separately verifiable by competent graduate students having to read no other parts but statements and definitions cited. Intuitive comments, examples and other comfort items are fat and skin: a lack or excess will not make the paper pretty. Proper scholarly references constitute clothing, no paper should ever appear in public without! The trains of thought which led to the discovery are blood and guts: keep them hidden. Other vital parts, like open problems, I skip out of modesty.

Writing Contributions.

Section 1 was prepared by Elena Temin, Yong Gao and Imre Kifor (BU), others by Berkeley students: 2.3 by Mark Sullivan, 3.0 by Eric Herrmann, 3.1 by Elena Eliashberg, 3.2 by Wayne Fenton and Peter Van Roy, 3.3 by Carl Ludewig, 3.4 by Sean Flynn, 3.4 by Francois Dumas, 4.1 by Jeff Makaiwi, 4.1.1 by Brian Jones and Carl Ludewig, 4.2 by David Leech and Peter Van Roy, 4.3 by Johnny and Siu-Ling Chan, 5.2 by Deborah Kordon, 5.3 by Carl Ludewig, 5.4 by Sean Flynn, Francois Dumas, Eric Herrmann, 5.5 by Brian Jones.

next up previous contents
Next: References Up: 5 Randomness in Computing. Previous: 5.4 Pseudo-randomness.

Leonid Levin
Wed Aug 21 20:35:42 EDT 1996