diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-10-24 15:33:07 +0200 |
commit | 162df3190c4e179ef968b0a467ddd4951faba336 (patch) | |
tree | 3c9628cf1abf259e1b897ac14b006e2b448cff27 /ss2017/cryptography/Notes06a.txt | |
parent | 92ed41381f40c97b52b0e96f0eaeaa9025091411 (diff) | |
download | uni-162df3190c4e179ef968b0a467ddd4951faba336.tar uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.gz uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.bz2 uni-162df3190c4e179ef968b0a467ddd4951faba336.tar.xz uni-162df3190c4e179ef968b0a467ddd4951faba336.zip |
Notes on cryptography
Diffstat (limited to 'ss2017/cryptography/Notes06a.txt')
-rw-r--r-- | ss2017/cryptography/Notes06a.txt | 105 |
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 @@ | |||
1 | |||
2 | |||
3 | Multiple encryptions from cpa-secure cryptosystem | ||
4 | - - - - - - - - - - - - - - - - - - - -- - - - - - | ||
5 | |||
6 | We have seen that a block cipher can be used repeatedly with the same | ||
7 | key (using e.g. CTR-mode) without compromising security. We show now | ||
8 | that this is true for an arbitrary cpa-secure cryptosystem. From a | ||
9 | practical point of view this is not so important because cpa-secure | ||
10 | cryptosystems typically come from block ciphers, and a block cipher is | ||
11 | used more efficiently through one of the modes of operation given. | ||
12 | |||
13 | However, the proof of the result (cpa->multiple) is interesting at | ||
14 | this point because it is the first time where we use semantic security | ||
15 | (here in the cpa sense) as an assumption rather than establishing | ||
16 | it. Furthermore, the result becomes practically relevant in the | ||
17 | context of public key cryptography where by definition security | ||
18 | against eavesdroppers and cpa security coincide. | ||
19 | |||
20 | Theorem. Let Pi=(Gen,Enc,Dec) be cpa-secure. Build | ||
21 | |||
22 | Pi'=(Gen,Enc',Dec') | ||
23 | |||
24 | Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2) | ||
25 | |||
26 | Then Pi' is cpa-secure, too. | ||
27 | |||
28 | Proof: Consider an adversary A' against Pi'. We run A' and answer | ||
29 | oracle queries honestly using Enc'_k. Adversary A' eventually | ||
30 | produces | ||
31 | |||
32 | m^0 = m1^0 || m2^0 | ||
33 | m^1 = m1^1 || m2^1 | ||
34 | |||
35 | and asks for a ciphertext c1 || c2. For b1,b2,b':{0,1} define | ||
36 | P(b1,b2,b') to be the probability that A' outputs b' when | ||
37 | c1<-Enc_k(m1^b1); c2<-Enc_k(m2^b2). | ||
38 | |||
39 | The success probability of A' equals 1/2 * (P(0,0,0) + P(1,1,1)) | ||
40 | |||
41 | The probabilities P(0,1,0) and P(0,1,1) are somewhat funny since they | ||
42 | correspond to replies to the adversary's question that are against | ||
43 | the rules. However, we still know that their sum is one and this can | ||
44 | be used as follows: | ||
45 | |||
46 | Let us design an adversary A against the original system Pi. This | ||
47 | adversary A produces m2^0 and m2^1 and receives a ciphertext c2 for | ||
48 | one of the two. It can then obtain c1<-Enc_k(m1^0), forward c1||c2 to | ||
49 | A' and output the bit b' it eventually receives from A'. The | ||
50 | probability that this bit is correct then is 1/2 P(0,0,0) + 1/2 | ||
51 | P(0,1,1) by making a case distinction over the equally likely | ||
52 | possibilities b=0 or b=1. So, assuming that Pi is cpa secure, we | ||
53 | obtain a negligible function negl(n) so that | ||
54 | |||
55 | 1/2 P(0,0,0) + 1/2 P(0,1,1) <= 1/2+negl(n) | ||
56 | |||
57 | Similarly, by producing m1^0 and m1^1 instead and using | ||
58 | c2<-Enc_k(m2^1), we obtain a bound | ||
59 | |||
60 | 1/2 P(0,1,0) + 1/2 P(1,1,1) <= 1/2+negl(n) | ||
61 | |||
62 | Summing up and using the fact that the sum of negligibles is | ||
63 | negligible we get | ||
64 | |||
65 | 1/2(P(0,0,0)+P(1,1,1)) + 1/2 <= 1 + negl(n) | ||
66 | and so 1/2(P(0,0,0)+P(1,1,1)) <= 1/2 + negl(n) QED. | ||
67 | |||
68 | Let us now consider the more general case where Pi is used to encode a | ||
69 | sequence of message of some arbitrary length l=l(n), i.e., depending | ||
70 | on n. Thus, define Pi'=(Gen,Enc',Dec') by | ||
71 | |||
72 | Enc'_k(m1||...||ml) = Enc_k(m1) || ... || Enc_k(ml) etc | ||
73 | |||
74 | Theorem: If Pi is cpa-secure so is Pi' as defined above. | ||
75 | |||
76 | Proof: The proof is similar to the one before. Adversary A' against | ||
77 | Pi' eventually produces m1^0...ml^0 and m1^1...ml^1 and waits for | ||
78 | ciphertexts c1..cl. For 0<=j<=l define P_j(b') to be the probability | ||
79 | that A' outputs b' assuming that | ||
80 | |||
81 | c1<-Enc_k(m1^0) ... cj<-Enc_k(mj^0), | ||
82 | c_{j+1}<-Enc_k(m_{j+1}^1) ... cl<-Enc_k(ml^1) | ||
83 | |||
84 | The success probability for A' is 1/2 * (P_l(0) + P_0(1)) and, as | ||
85 | before, we should bound this by 1/2+negl(n). | ||
86 | |||
87 | For the skew probabilities it holds as before P_j(0)+P_j(1)=1. | ||
88 | |||
89 | For each t=1..l we build an adversary A_t against Pi by outputting | ||
90 | mt^0 and mt^1, receiving ct, requesting c1<-Enc_k(m1^0), | ||
91 | c2<-Enc_k(m2^0) ... c_{t-1}<-Enc_k(m_{t-1}^0), | ||
92 | c_{t+1}<-Enc_k(m_{t+1}^1)...c_l<-Enc_k(m_l^1). Notice the switch from | ||
93 | ^0 to ^1 after we reach t. Adversary A_t then forwards c1..cl to A' | ||
94 | and returns its answer. The success probability is | ||
95 | 1/2(P_{t}(0)+P_{t-1}(1)) which is hence bounded by 1/2 + negl(n): | ||
96 | |||
97 | For all t=1..l : 1/2(P_t(0)+P_{t-1}(1)) <= 1/2+negl(n) | ||
98 | |||
99 | Summing all these inequalities noticing P_t(0)+P_t(1)=1 yields | ||
100 | |||
101 | 1/2(P_l(0) + (l-1)*1 + P_0(1)) <= 1/2*l + negl(n) /* another | ||
102 | negligible function */ | ||
103 | |||
104 | and thus 1/2(P_l(0) + P_0(1)) <= 1/2 + negl(n) as required. QED | ||
105 | |||