path: root/ss2017/cryptography/Notes05.txt

5 Security against chosen plaintext attacks (KL3.5)
---------------------------------------------------

We now consider security of cryptosystems against stronger adversaries
which may request the encryption of arbitrary plaintexts of their
choice. There are some practical scenarios where this might occur,
e.g. a smartcard which can be interacted with arbitrarily or by
preparing some situation whose description will then be transmitted by
the opposite party in encrpyted form.


Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment
PrivK^cpa_{A,Pi}(n) is now defined as follows:


  1. Key k is generated by Gen(n)
  2. The adversary A is given the security parameter n and the procedure
     Enc_k as a black box (oracle access). After some interaction with
     the oracle it then outputs two messages m0 and m1 from {0,1}^{l(n)}
     (or of the same length in the case of variable length schemes).
  3. A  bit b <- {0,1} is chosen uniformly at random (50/50). The
     (or rather a) ciphertext  c = Enc_k(m_b) is given to A.
  4. A continues to have oracle access to Enc_k and then answers by
     outputting a bit b'.
  4. The output of the experiment is defined 1 if b=b' and 0 otherwise.


Definition: A scheme Pi=(Gen,Enc,Dec) has *indistinguishable
encryptions under a chosen plaintext attack* (is cpa-secure for short)
if there is a negligible function negl(n) such that for all (pr.-polytime)
adversaries A

      Pr[PrivK^cpa_{A,Pi}(n) = 1] <= 1/2 + negl(n)

There is also a "known plaintext version" where the adversary does not
get full-blown oracle access to Enc_k but can merely request
encryptions of a previously submitted list of plaintexts. The details
of this are left to the reader.

We first notice that no deterministic scheme can possibly be
cpa-secure. Given c simply compute (using the oracle) c_0=Enc_k(m_0)
and c_1=Enc_k(m_1) and return b' such that c_b'=c. Thus, any cpa-secure
scheme must include a random element into the encryption. But naive
ways of doing so will not be successful either. Suppose for example
that Pi=(Gen,Enc,Dec,l) is a deterministic scheme, i.e. Enc_k( ) is a
function. Design a new scheme Pi' as follows:

For bitstrings u,v we let u || v stand for the concatenation of u and
v. If w is a bitstring of even length 2n then we let w.1 and w.2 stand
for its first and second halves.

Gen' = Gen
l'(n) = l(n)/2 /* w.l.o.g. l(n) is even */
Enc'_k(m) = Enc_k(r || m) where r is a random bitstring
             of length l(n)/2.
Dec'_k(c) = Dec_k(c).1

Clearly, Pi' has indistinguishable encryptions in the presence of an
eavesdropper if Pi has, but Pi' does not in general withstand chosen
plaintext attacks. Namely, consider that Enc_k(m)=G(k)+m as above. We
then have Enc'_k(m) = G(k).1 + r || G(k).2 + m.  As a result, the
adversary can take the first half of the received ciphertext c,
request encryptions c_0 nd c_1 of m_0 and m_1 and determine b' so that
c.1 = (c_b').1 .

In order to achieve the desired security we need a *pseudorandom function*

Definition: A pseudorandom function (PRF) is a binary function on bitstrings

                F : {0,1}^* x {0,1}^* -> {0,1}^*

with application F(k,x) written F_k(x) such that

 1) |k|=|x| implies |F_k(x)|=|k|=|x| (and F need not be defined on
    arguments of different length)

 2) F is deterministic, polynomial-time computable

 3) For all probabilistic polynomial-time distinguishers D and all n
    one has

     | Pr[ D^{F_k()}(n)=1 ] - Pr[D^{f()}(n)=1] | = negl(n)

    for some negligible function negl() and probabilities taken over
    k and f(), see below.

The distinguisher has access to an oracle, i.e. a subroutine of type
{0,1}^n->{0,1}^n. In the experiment, first k:{0,1}^n is drawn
uniformly at random and then a function f from {0,1}^n->{0,1}^n is
drawn uniformly at random (from the 2^{n*2^n} many possibilities). The
oracle is then instantiated with F_k() on the one hand and
with f on the other. The probabilities for the distinguisher to output
1 in either case should differ only negligibly.

So, where a pseudorandom generator expands a size n key k to a size
l(n) bitstring that looks random a pseudorandom function expands a
size n key to a function F_k which could be written as a size n*2^n
bitstring. Again, this "very large" object should look
random. However, only a polynomial portion of it can be examined by
the distinguisher. On the other hand, which portion that is is up to
the distinguisher to decide and not priori fixed.

We remark that one often uses variants of PRF where the size of
argument x and results are functions of a security parameter other
than the identity function. (The security parameter must then be
supplied explicitly to F)

Relationship between PRF and PRG:

It is not hard to see that every PRF can serve as a PRG. Given k
simply output the string F(k,0) || F(k,1) || F(k,2) || ... || F(k,N) for
sufficiently large N and where e.g. 2 stands for the encoding of 2 as
a length n bitstring. If a distinguisher could tell this from a random
string one could easily use it to distinguish F_k from a random
function. Surprisingly, the converse also holds, see (KL6.5). However,
we still do not know whether PRG exist.  In practice, PRF are
constructed using heuristic approaches.


A CPA-secure cryptosystem from a PRF (KL3.6.2)
- - - - - - - - - - - - - - - - - - - - - - - -

Here is, how we use a PRF to construct a CPA-secure cryptosystem. Note
that by our earlier observation the scheme itself must be randomised.


Gen(n): return a random bitstring of length n as key.
Enc_k(m): choose r:{0,1}^n uniformly at random and output the ciphertext
            c := r || F_k(r)+m
Dec_k(c): given c extract c.1=r and c.2=F_k(r)+m then return c.2+F_k(r)

Notice that Dec_k(Enc_k(m)) = F(k,r)+F(k,r)+m = m

Remark: A random element like r added to a piece of data is known as a
*nonce*.

Theorem: If F is a PRF then the above construction yields a fixed
length (l(n)=n) CPA-secure cryptosystem.

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

Given security parameter n and oracle access to a function h (which is
instantiated as either F_k() or a truly random f()) the distinguisher
begins by passing the security parameter n to the adversary A.

Now, whenever the adversary queries its own oracle which it assumes to
be of the form Enc_k() then the distinguisher chooses r:{0,1}^n at
random and returns r || h(r)+m to A.

When the adversary enters the second phase and outputs two messages
m_0, m_1 to distinguish based on their encryptions the distinguisher
then chooses a random bit b:{0,1} and r:{0,1}^n uniformly at random
and returns r || h(r)+m_b to A. Further oracle queries from A are
answered as before.

When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise.
Let us see what the adversary can do when h is a truly random
function. Unlike in the "eavesdropper" case, A has a certain
advantage: namely suppose it has already requested encryptions c_0 and
c_1 of the messages m_0 and m_1 it then forwards (and it would be
"wise" for A to do so). If it now happens by accident that
c.1=c_0.1=c_1.1, i.e. the three random nonces used were all equal,
then since the rest is deterministic, the adversary can pick b' such
that c.2=c_{b'}.2 and be correct. Since, however, the adversary can
only make polynomially many queries the likelihood for this to happen
is negligible. If, however, the random nonce used in the preparation
of c is different from all the ones used in oracle queries then c
looks completely random to A and its success probability is exactly
1/2. Summing up, if h is truly random then A's success probability is
1/2+negl(n).

If, on the other hand, h is F_k(), then let p be the success
probability of the adversary A on our new cryptosystem. It is clear
that our distinguisher will output 1 with probability p for we have
used A according to the rules of the PrivK^cpa-experiment. Since F was
assumed to be a PRF we thus know that |p-(1/2+negl(n))| is itself
negligible. It then follows that p is bounded by 1/2 plus a negligible
function.                                                      Q.E.D.


Notice that this proof newly introduces negligible probabilities
rather than (or in addition to) just move them around and thus gives
further evidence as to why allowing negligible deviations from the
ideal situation is reasonable.

We also remark that the way the system was presented the length of the
key equals that of the message. However, in the case of a CPA-secure
system we can encrypt several messages with the same key without
compromising security. We generalise this idea in the next chapter.

Proposition: Let Pi=(Gen,Enc,Dec) be cpa-secure and define
Pi'=(Gen,Enc',Dec') by Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2). Then
Pi' is cpa-secure. Here m1, m2, as well as, c1,c2 are assumed to be of
equal length.

Proof: From a hypothetical cpa-adversary A' against Pi' we construct a
cpa-adversary A against the original system Pi as follows:

A runs A' and answers any oracle requests according to Pi'. E.g. if A'
asks for an encryption of m1||m2 it requests encryptions c1 and c2 of
m1, m2, respectively and then provides the answer c1||c2.

When A' outputs the challenge m1^0||m2^0 vs m1^1||m2^1 A submits the
challenge m2^0 vs m2^1 and receives a ciphertext c2 (which should be an
encryption of m2^0 or m2^1). A then requests an encryption c1 of m1^0 and
passes c1||c2 to A'.

The answer bit b' supplied by A' is then output.

Let p be the success probability of A'.

If the secret bit b is equal to 0 then the
success probability of A is p as well.