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/Notes05.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/Notes05.txt')
-rw-r--r-- | ss2017/cryptography/Notes05.txt | 217 |
1 files changed, 217 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes05.txt b/ss2017/cryptography/Notes05.txt new file mode 100644 index 0000000..beca359 --- /dev/null +++ b/ss2017/cryptography/Notes05.txt | |||
@@ -0,0 +1,217 @@ | |||
1 | 5 Security against chosen plaintext attacks (KL3.5) | ||
2 | --------------------------------------------------- | ||
3 | |||
4 | We now consider security of cryptosystems against stronger adversaries | ||
5 | which may request the encryption of arbitrary plaintexts of their | ||
6 | choice. There are some practical scenarios where this might occur, | ||
7 | e.g. a smartcard which can be interacted with arbitrarily or by | ||
8 | preparing some situation whose description will then be transmitted by | ||
9 | the opposite party in encrpyted form. | ||
10 | |||
11 | |||
12 | Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment | ||
13 | PrivK^cpa_{A,Pi}(n) is now defined as follows: | ||
14 | |||
15 | |||
16 | 1. Key k is generated by Gen(n) | ||
17 | 2. The adversary A is given the security parameter n and the procedure | ||
18 | Enc_k as a black box (oracle access). After some interaction with | ||
19 | the oracle it then outputs two messages m0 and m1 from {0,1}^{l(n)} | ||
20 | (or of the same length in the case of variable length schemes). | ||
21 | 3. A bit b <- {0,1} is chosen uniformly at random (50/50). The | ||
22 | (or rather a) ciphertext c = Enc_k(m_b) is given to A. | ||
23 | 4. A continues to have oracle access to Enc_k and then answers by | ||
24 | outputting a bit b'. | ||
25 | 4. The output of the experiment is defined 1 if b=b' and 0 otherwise. | ||
26 | |||
27 | |||
28 | Definition: A scheme Pi=(Gen,Enc,Dec) has *indistinguishable | ||
29 | encryptions under a chosen plaintext attack* (is cpa-secure for short) | ||
30 | if there is a negligible function negl(n) such that for all (pr.-polytime) | ||
31 | adversaries A | ||
32 | |||
33 | Pr[PrivK^cpa_{A,Pi}(n) = 1] <= 1/2 + negl(n) | ||
34 | |||
35 | There is also a "known plaintext version" where the adversary does not | ||
36 | get full-blown oracle access to Enc_k but can merely request | ||
37 | encryptions of a previously submitted list of plaintexts. The details | ||
38 | of this are left to the reader. | ||
39 | |||
40 | We first notice that no deterministic scheme can possibly be | ||
41 | cpa-secure. Given c simply compute (using the oracle) c_0=Enc_k(m_0) | ||
42 | and c_1=Enc_k(m_1) and return b' such that c_b'=c. Thus, any cpa-secure | ||
43 | scheme must include a random element into the encryption. But naive | ||
44 | ways of doing so will not be successful either. Suppose for example | ||
45 | that Pi=(Gen,Enc,Dec,l) is a deterministic scheme, i.e. Enc_k( ) is a | ||
46 | function. Design a new scheme Pi' as follows: | ||
47 | |||
48 | For bitstrings u,v we let u || v stand for the concatenation of u and | ||
49 | v. If w is a bitstring of even length 2n then we let w.1 and w.2 stand | ||
50 | for its first and second halves. | ||
51 | |||
52 | Gen' = Gen | ||
53 | l'(n) = l(n)/2 /* w.l.o.g. l(n) is even */ | ||
54 | Enc'_k(m) = Enc_k(r || m) where r is a random bitstring | ||
55 | of length l(n)/2. | ||
56 | Dec'_k(c) = Dec_k(c).1 | ||
57 | |||
58 | Clearly, Pi' has indistinguishable encryptions in the presence of an | ||
59 | eavesdropper if Pi has, but Pi' does not in general withstand chosen | ||
60 | plaintext attacks. Namely, consider that Enc_k(m)=G(k)+m as above. We | ||
61 | then have Enc'_k(m) = G(k).1 + r || G(k).2 + m. As a result, the | ||
62 | adversary can take the first half of the received ciphertext c, | ||
63 | request encryptions c_0 nd c_1 of m_0 and m_1 and determine b' so that | ||
64 | c.1 = (c_b').1 . | ||
65 | |||
66 | In order to achieve the desired security we need a *pseudorandom function* | ||
67 | |||
68 | Definition: A pseudorandom function (PRF) is a binary function on bitstrings | ||
69 | |||
70 | F : {0,1}^* x {0,1}^* -> {0,1}^* | ||
71 | |||
72 | with application F(k,x) written F_k(x) such that | ||
73 | |||
74 | 1) |k|=|x| implies |F_k(x)|=|k|=|x| (and F need not be defined on | ||
75 | arguments of different length) | ||
76 | |||
77 | 2) F is deterministic, polynomial-time computable | ||
78 | |||
79 | 3) For all probabilistic polynomial-time distinguishers D and all n | ||
80 | one has | ||
81 | |||
82 | | Pr[ D^{F_k()}(n)=1 ] - Pr[D^{f()}(n)=1] | = negl(n) | ||
83 | |||
84 | for some negligible function negl() and probabilities taken over | ||
85 | k and f(), see below. | ||
86 | |||
87 | The distinguisher has access to an oracle, i.e. a subroutine of type | ||
88 | {0,1}^n->{0,1}^n. In the experiment, first k:{0,1}^n is drawn | ||
89 | uniformly at random and then a function f from {0,1}^n->{0,1}^n is | ||
90 | drawn uniformly at random (from the 2^{n*2^n} many possibilities). The | ||
91 | oracle is then instantiated with F_k() on the one hand and | ||
92 | with f on the other. The probabilities for the distinguisher to output | ||
93 | 1 in either case should differ only negligibly. | ||
94 | |||
95 | So, where a pseudorandom generator expands a size n key k to a size | ||
96 | l(n) bitstring that looks random a pseudorandom function expands a | ||
97 | size n key to a function F_k which could be written as a size n*2^n | ||
98 | bitstring. Again, this "very large" object should look | ||
99 | random. However, only a polynomial portion of it can be examined by | ||
100 | the distinguisher. On the other hand, which portion that is is up to | ||
101 | the distinguisher to decide and not priori fixed. | ||
102 | |||
103 | We remark that one often uses variants of PRF where the size of | ||
104 | argument x and results are functions of a security parameter other | ||
105 | than the identity function. (The security parameter must then be | ||
106 | supplied explicitly to F) | ||
107 | |||
108 | Relationship between PRF and PRG: | ||
109 | |||
110 | It is not hard to see that every PRF can serve as a PRG. Given k | ||
111 | simply output the string F(k,0) || F(k,1) || F(k,2) || ... || F(k,N) for | ||
112 | sufficiently large N and where e.g. 2 stands for the encoding of 2 as | ||
113 | a length n bitstring. If a distinguisher could tell this from a random | ||
114 | string one could easily use it to distinguish F_k from a random | ||
115 | function. Surprisingly, the converse also holds, see (KL6.5). However, | ||
116 | we still do not know whether PRG exist. In practice, PRF are | ||
117 | constructed using heuristic approaches. | ||
118 | |||
119 | |||
120 | A CPA-secure cryptosystem from a PRF (KL3.6.2) | ||
121 | - - - - - - - - - - - - - - - - - - - - - - - - | ||
122 | |||
123 | Here is, how we use a PRF to construct a CPA-secure cryptosystem. Note | ||
124 | that by our earlier observation the scheme itself must be randomised. | ||
125 | |||
126 | |||
127 | Gen(n): return a random bitstring of length n as key. | ||
128 | Enc_k(m): choose r:{0,1}^n uniformly at random and output the ciphertext | ||
129 | c := r || F_k(r)+m | ||
130 | Dec_k(c): given c extract c.1=r and c.2=F_k(r)+m then return c.2+F_k(r) | ||
131 | |||
132 | Notice that Dec_k(Enc_k(m)) = F(k,r)+F(k,r)+m = m | ||
133 | |||
134 | Remark: A random element like r added to a piece of data is known as a | ||
135 | *nonce*. | ||
136 | |||
137 | Theorem: If F is a PRF then the above construction yields a fixed | ||
138 | length (l(n)=n) CPA-secure cryptosystem. | ||
139 | |||
140 | Proof: Let Pi stand for the scheme constructed above from F and | ||
141 | l(n). Assume further, that A is an adversary against Pi. We construct | ||
142 | from A a distinguisher D for the PRF F as follows: | ||
143 | |||
144 | Given security parameter n and oracle access to a function h (which is | ||
145 | instantiated as either F_k() or a truly random f()) the distinguisher | ||
146 | begins by passing the security parameter n to the adversary A. | ||
147 | |||
148 | Now, whenever the adversary queries its own oracle which it assumes to | ||
149 | be of the form Enc_k() then the distinguisher chooses r:{0,1}^n at | ||
150 | random and returns r || h(r)+m to A. | ||
151 | |||
152 | When the adversary enters the second phase and outputs two messages | ||
153 | m_0, m_1 to distinguish based on their encryptions the distinguisher | ||
154 | then chooses a random bit b:{0,1} and r:{0,1}^n uniformly at random | ||
155 | and returns r || h(r)+m_b to A. Further oracle queries from A are | ||
156 | answered as before. | ||
157 | |||
158 | When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise. | ||
159 | Let us see what the adversary can do when h is a truly random | ||
160 | function. Unlike in the "eavesdropper" case, A has a certain | ||
161 | advantage: namely suppose it has already requested encryptions c_0 and | ||
162 | c_1 of the messages m_0 and m_1 it then forwards (and it would be | ||
163 | "wise" for A to do so). If it now happens by accident that | ||
164 | c.1=c_0.1=c_1.1, i.e. the three random nonces used were all equal, | ||
165 | then since the rest is deterministic, the adversary can pick b' such | ||
166 | that c.2=c_{b'}.2 and be correct. Since, however, the adversary can | ||
167 | only make polynomially many queries the likelihood for this to happen | ||
168 | is negligible. If, however, the random nonce used in the preparation | ||
169 | of c is different from all the ones used in oracle queries then c | ||
170 | looks completely random to A and its success probability is exactly | ||
171 | 1/2. Summing up, if h is truly random then A's success probability is | ||
172 | 1/2+negl(n). | ||
173 | |||
174 | If, on the other hand, h is F_k(), then let p be the success | ||
175 | probability of the adversary A on our new cryptosystem. It is clear | ||
176 | that our distinguisher will output 1 with probability p for we have | ||
177 | used A according to the rules of the PrivK^cpa-experiment. Since F was | ||
178 | assumed to be a PRF we thus know that |p-(1/2+negl(n))| is itself | ||
179 | negligible. It then follows that p is bounded by 1/2 plus a negligible | ||
180 | function. Q.E.D. | ||
181 | |||
182 | |||
183 | Notice that this proof newly introduces negligible probabilities | ||
184 | rather than (or in addition to) just move them around and thus gives | ||
185 | further evidence as to why allowing negligible deviations from the | ||
186 | ideal situation is reasonable. | ||
187 | |||
188 | We also remark that the way the system was presented the length of the | ||
189 | key equals that of the message. However, in the case of a CPA-secure | ||
190 | system we can encrypt several messages with the same key without | ||
191 | compromising security. We generalise this idea in the next chapter. | ||
192 | |||
193 | Proposition: Let Pi=(Gen,Enc,Dec) be cpa-secure and define | ||
194 | Pi'=(Gen,Enc',Dec') by Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2). Then | ||
195 | Pi' is cpa-secure. Here m1, m2, as well as, c1,c2 are assumed to be of | ||
196 | equal length. | ||
197 | |||
198 | Proof: From a hypothetical cpa-adversary A' against Pi' we construct a | ||
199 | cpa-adversary A against the original system Pi as follows: | ||
200 | |||
201 | A runs A' and answers any oracle requests according to Pi'. E.g. if A' | ||
202 | asks for an encryption of m1||m2 it requests encryptions c1 and c2 of | ||
203 | m1, m2, respectively and then provides the answer c1||c2. | ||
204 | |||
205 | When A' outputs the challenge m1^0||m2^0 vs m1^1||m2^1 A submits the | ||
206 | challenge m2^0 vs m2^1 and receives a ciphertext c2 (which should be an | ||
207 | encryption of m2^0 or m2^1). A then requests an encryption c1 of m1^0 and | ||
208 | passes c1||c2 to A'. | ||
209 | |||
210 | The answer bit b' supplied by A' is then output. | ||
211 | |||
212 | Let p be the success probability of A'. | ||
213 | |||
214 | If the secret bit b is equal to 0 then the | ||
215 | success probability of A is p as well. | ||
216 | |||
217 | |||