1 files changed, 105 insertions, 0 deletions

diff --git a/ss2017/cryptography/Notes06a.txt b/ss2017/cryptography/Notes06a.txt
new file mode 100644
index 0000000..6791ce9
--- /dev/null
+++ b/ss2017/cryptography/Notes06a.txt
@@ -0,0 +1,105 @@
+
+
+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
+