From 162df3190c4e179ef968b0a467ddd4951faba336 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 24 Oct 2017 15:33:07 +0200 Subject: Notes on cryptography --- ss2017/cryptography/Notes06a.txt | 105 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 105 insertions(+) create mode 100644 ss2017/cryptography/Notes06a.txt (limited to 'ss2017/cryptography/Notes06a.txt') 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 + -- cgit v1.2.3