Multiple encryptions from cpa-secure cryptosystem
- - - - - - - - - - - - - - - - - - - -- - - - - -

We have seen that a block cipher can be used repeatedly with the same
key (using e.g. CTR-mode) without compromising security. We show now
that this is true for an arbitrary cpa-secure cryptosystem. From a
practical point of view this is not so important because cpa-secure
cryptosystems typically come from block ciphers, and a block cipher is
used more efficiently through one of the modes of operation given.

However, the proof of the result (cpa->multiple) is interesting at
this point because it is the first time where we use semantic security
(here in the cpa sense) as an assumption rather than establishing
it. Furthermore, the result becomes practically relevant in the
context of public key cryptography where by definition security
against eavesdroppers and cpa security coincide.

Theorem. Let Pi=(Gen,Enc,Dec) be cpa-secure. Build

Pi'=(Gen,Enc',Dec')

Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2)

Then Pi' is cpa-secure, too.

Proof: Consider an adversary A' against Pi'.  We run A' and answer
oracle queries honestly using Enc'_k.  Adversary A' eventually
produces

m^0 = m1^0 || m2^0
m^1 = m1^1 || m2^1

and asks for a ciphertext c1 || c2.  For b1,b2,b':{0,1} define
P(b1,b2,b') to be the probability that A' outputs b' when
c1<-Enc_k(m1^b1); c2<-Enc_k(m2^b2).

The success probability of A' equals  1/2 * (P(0,0,0) + P(1,1,1))

The probabilities P(0,1,0) and P(0,1,1) are somewhat funny since they
correspond to replies to the adversary's question that are against
the rules. However, we still know that their sum is one and this can
be used as follows:

Let us design an adversary A against the original system Pi. This
adversary A produces m2^0 and m2^1 and receives a ciphertext c2 for
one of the two. It can then obtain c1<-Enc_k(m1^0), forward c1||c2 to
A' and output the bit b' it eventually receives from A'. The
probability that this bit is correct then is 1/2 P(0,0,0) + 1/2
P(0,1,1) by making a case distinction over the equally likely
possibilities b=0 or b=1. So, assuming that Pi is cpa secure, we
obtain a negligible function negl(n) so that

1/2 P(0,0,0) + 1/2 P(0,1,1) <= 1/2+negl(n)

Similarly, by producing m1^0 and m1^1 instead and using
c2<-Enc_k(m2^1), we obtain a bound

1/2 P(0,1,0) + 1/2 P(1,1,1) <= 1/2+negl(n)

Summing up and using the fact that the sum of negligibles is
negligible we get

1/2(P(0,0,0)+P(1,1,1)) + 1/2 <= 1 + negl(n) 
and so 1/2(P(0,0,0)+P(1,1,1))  <= 1/2 + negl(n)  QED. 

Let us now consider the more general case where Pi is used to encode a
sequence of message of some arbitrary length l=l(n), i.e., depending
on n. Thus, define Pi'=(Gen,Enc',Dec') by

Enc'_k(m1||...||ml) = Enc_k(m1) || ... || Enc_k(ml) etc

Theorem: If Pi is cpa-secure so is Pi' as defined above.

Proof: The proof is similar to the one before. Adversary A' against
Pi' eventually produces m1^0...ml^0 and m1^1...ml^1 and waits for
ciphertexts c1..cl. For 0<=j<=l define P_j(b') to be the probability
that A' outputs b' assuming that

c1<-Enc_k(m1^0) ... cj<-Enc_k(mj^0),
c_{j+1}<-Enc_k(m_{j+1}^1) ... cl<-Enc_k(ml^1)

The success probability for A' is 1/2 * (P_l(0) + P_0(1)) and, as
before, we should bound this by 1/2+negl(n).

For the skew probabilities it holds as before P_j(0)+P_j(1)=1.

For each t=1..l we build an adversary A_t against Pi by outputting
mt^0 and mt^1, receiving ct, requesting c1<-Enc_k(m1^0),
c2<-Enc_k(m2^0) ... c_{t-1}<-Enc_k(m_{t-1}^0),
c_{t+1}<-Enc_k(m_{t+1}^1)...c_l<-Enc_k(m_l^1). Notice the switch from
^0 to ^1 after we reach t. Adversary A_t then forwards c1..cl to A'
and returns its answer. The success probability is
1/2(P_{t}(0)+P_{t-1}(1)) which is hence bounded by 1/2 + negl(n):

For all t=1..l : 1/2(P_t(0)+P_{t-1}(1)) <= 1/2+negl(n)

Summing all these inequalities noticing P_t(0)+P_t(1)=1 yields

1/2(P_l(0) + (l-1)*1 +  P_0(1)) <= 1/2*l + negl(n) /* another
                                            negligible function */

and thus 1/2(P_l(0) + P_0(1)) <= 1/2 + negl(n) as required. QED