4 Pseudorandomness (3.3)
------------------------

In order to arrive at cryptosystems with keys considerably shorter
than messages it is natural to use a generator which from a truly
random seed produces (deterministically!) a sequence of bits that
looks random. Indeed, such generators are often used in the
implementation of random in standard libraries e.g. for C or Java.

The question is whether a so constructed cryptosystem might be while
not perfectly secret still enjoy semantic security.  The answer is yes
if the generator is a *pseudorandom generator*, PRG for short, in the
following sense.

Definition (pseudorandom generator): Let l(n) be a polynomial and G a
deterministic polynomial time algorithm that for any bitstring s of
length n outputs a bitstring G(s) of length l(n). We call G a
*pseudorandom generator* with expansion l(n) if for any probabilistic
polynomial time adversary D ("distinguisher") it holds that

 | Pr[D(r)=1] - Pr[D(G(s))=1] |  = negl(n)

for some negligible function negl(n) and for all n.  Here s and r are
bitstrings of lengths n and l(n), respectively, chosen uniformly at
random.

We remark that if l(n)=n then G(s)=s is trivially a pseudorandom
generator and if l(n)>n and G is any function sending length n
bitstrings to length l(n) bitstrings will be vulnerable against
distinguishers with exponential computing power. Simply let D
enumerate all length n bitstrings s' and check for each of them
whether its input equals G(s'). Return 1 if yes, 0 otherwise. When fed
G(s) the distinguisher will output 1 with certainty and if fed a
random string then it will output one with probability 2^{-(l(n)-n)}
only. The difference between these probabilities is not negligible.

In summary, pseudorandom strings are as good as truly random ones so
long as they are used in a probabilistic polynomial time context and
one accepts negligible probability of failure.

Unfortunately, one does not know whether there exist PRG with l(n)>n
at all, but it is generally believed that they do. At least, there do
exist several such objects for which no (probabilistic, polynomial
time) distinguisher is currently known despite a lot of research.


Semantically secure cryptosystems from PRG (KL3.4.1)
- - - - - - - - - - - - - - - - - - - - - - - - - - 

Assuming that we have a PRG G with expansion factor l(n). We can use
it in order to construct a semantically secure fixed-length encryption
scheme for messages of length l(n) as follows:

Gen(n): return a random bitstring of length n as key.
Enc_k(m): return G(k)+m /* + = bitwise XOR */
Dec_k(c): return G(k)+c

Notice that Dec_k(Enc_k(m)) = G(k)+G(k)+m = m

Theorem: If G is a PRG of expansion l then the above construction has
indistinguishable encryptions in the presence of an eavesdropper.

Proof: Let Pi stand for the scheme constructed above from G and
l(n). Assume further, that A is an adversary against Pi. We construct
from A a distinguisher D as follows:

Given a string w (either random or of the form G(s)) the distinguisher
begins by letting the assumed adversary A produce two messages m0 and
m1. It then selects b:{0,1} at random and sends m_b + w to the adversary A.
If A outputs b the distinguisher returns 1 and it returns
0 otherwise. Let p be the success probability of A in the PrivK^eav
experiment which must be shown to be 0.5+negl(n). If w is truly random
then so is m_b+w and the chance that A finds out b is exactly 1/2. If,
on the other hand, w is G(s) for random s, then this likelihood is
p. The difference between the two, i.e. p-1/2 is negligible since G
was assumed to be a PRG and as a result p=1/2+negl(n) as required.
Q.E.D.