Public key cryptography 

- making encryption method public while
keeping decryption method secret

- make use of the fact that there are computational problems or
functions f, which are easy to compute but difficult to invert.

Example of such ``one-way'' functions - In a phone book, it is easy to
find the number of a specific person, but given a specified number, it
is almost impossible to find the person with that number within a
reasonable amount of time.

Note: there is a still one-to-one correspondence between a specific
person and his/her phone number.

Terminology:

Plaintext - original message
Cryptotext - encrypted message


Example: Public-key cryptosystem using the one-way function based on
the phone book

Encryption (context free):

1) For each letter of the plaintext, a name beginning with that letter is
chosen from the phone book. 

2) The corresponding phone number is used to encrypt that particular
occurence of the letter in question.

e.g.    Plaintext     Name chosen randomly      Cryptotext
        --------------------------------------------------
        
          C               Cobham                  718424
          O               Ogden                   245358
          M               Maurer                  887230
          E               Engeler                 587121
 

3) The whole cryptotext is obtained by writing, one after the other,
all numbers appearing in the right column. 

Note: The above encryption is nondeterministic - two different
occurrences of the same letter are very unlikely to be encrypted in
the same way. Many different cryptotexts result from the same text,
but each cryptotext gives rise to only one plaintext.

Decryption: 

A legal receiver of the plaintext message would have a ``reverse''
directory listed according to the increasing order of the numbers
(together with the names of the corresponding persons).  With this
reverse directory, looking up a letter that corresponds to each number
is easy (because the numbers are listed in increasing order).

Such a reverse directory constitutes a ``trapdoor'' known only
to the legal users of the system.

Without this trapdoor, an outsider cannot interpret the number
sequence intercepted (within a reasonable amount of time), though the
encryption method is publicized.


Formal definition of a one-way function f():

Given an argument value x, it is easy to compute the function value
f(x), whereas it is computationally intractable to compute x from f(x). 

Note: the computation of x from f(x) should be intractable for an
outsider only. But a legal receiver should have a trapdoor that makes
it easy to compute x from f(x).

Currently, there is no mathematical proof that such a one-way function
exists, but there are many functions that are ``believed'' to be
one-way in the above sense, i.e., there are many functions such that

1) it is easy to compute f(x) given x;

2) An efficient algorithm to compute x from f(x) is not known.