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/Notes03.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/Notes03.txt')
-rw-r--r-- | ss2017/cryptography/Notes03.txt | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes03.txt b/ss2017/cryptography/Notes03.txt new file mode 100644 index 0000000..fb94b87 --- /dev/null +++ b/ss2017/cryptography/Notes03.txt | |||
@@ -0,0 +1,100 @@ | |||
1 | |||
2 | |||
3 | 3 Semantic Security (KL3.1, KL3.2) | ||
4 | ---------------------------------- | ||
5 | |||
6 | In order to formally study secrecy of schemes that use shorter keys | ||
7 | one must somehow incorporate the computational power of an | ||
8 | adversary. One way of doing this is to use concrete bounds: | ||
9 | |||
10 | A scheme is (t,epsilon)-secure if every adversary running for time t | ||
11 | succeeds in breaking the scheme (in the appropriate sense) with | ||
12 | probability at most epsilon. | ||
13 | |||
14 | For example, if we use keys of bit length n and the only possible | ||
15 | attack is by trying out all keys (this happens e.g. with Vernam's | ||
16 | cipher) then assuming that 10^9 keys can be tried out every second | ||
17 | (1GHz) trying out 2^60 operations takes 35years thus several years | ||
18 | even with highly parallel computers. Thus, a 60bit key takes this time | ||
19 | to be broken with certainty, a 64 bit key takes this time to be broken | ||
20 | with probability 1/16 etc. Currently, one recommends key lengths of | ||
21 | 128bit (128 *bits of security*) to make the success probability | ||
22 | negligible (e.g. lower than that of a meteor crashing into the device) | ||
23 | and to allow for future technological advances. | ||
24 | |||
25 | Now, working with concrete runtimes and probabilities is difficult and | ||
26 | brittle because of its dependency on concrete hardware configuration, | ||
27 | programming language, implementation details, etc. As a result, one | ||
28 | uses instead an asymptotic approach where runtimes and probabilities | ||
29 | as well as sizes of keys and texts are functions of a *security | ||
30 | parameter* n. One then wants that the success probability of an | ||
31 | adversary whose runtime is polynomial in the security parameter is a | ||
32 | *negligible function* of the security parameter, i.e. smaller than n^k | ||
33 | for any k. | ||
34 | |||
35 | Definition: A private-key encryption scheme is a tuple of | ||
36 | probabilistic polynomial-time algorithms (Gen,Enc,Dec) such that: | ||
37 | |||
38 | 1. Gen computes a key (in {0,1}^*) from the security parameter | ||
39 | (presented in unary, i.e. as 1...1 (n times)). We write this as k <- | ||
40 | Gen(n) or k <- Gen(1^n) to emphasize the unary notation. | ||
41 | |||
42 | 2. Enc_k(m) and Dec_k(c) are as before, except that m, c are | ||
43 | bitsequences (in {0,1}^*). In particular, we must have Dec_k(Enc_k(m))=m. | ||
44 | |||
45 | A fixed-length private-key encryption scheme is defined analogously, | ||
46 | but there is a function l(n) fixing the length of plaintexts as a | ||
47 | function of the security parameter. Formally, when k is returned from | ||
48 | Gen(n) then Dec_k(m) is defined only for m of length exactly l(n). | ||
49 | |||
50 | For example, the one-time pad can be cast into this framework. Given | ||
51 | the security parameter n, Gen generates a random bit sequence of | ||
52 | length n. One has l(n)=n and Enc_k(m) = m+k etc. | ||
53 | |||
54 | |||
55 | |||
56 | Indistinguishability in the presence of an eavesdropper | ||
57 | - - - - - - - - - - - - - - - - - - - - - - - - - - - - | ||
58 | |||
59 | We now want to adapt the notion of perfect secrecy from above to the | ||
60 | asymptotic framework. An adversary thus also gets the security | ||
61 | parameter n and its runtime must be bounded by a polynomial in n. It | ||
62 | is allowed to use randomization (has access to random bits). | ||
63 | |||
64 | Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment | ||
65 | PrivK^eav_{A,Pi}(n) is now defined as follows: | ||
66 | |||
67 | |||
68 | 1. The adversary produces two messages m0, m1 of equal length | ||
69 | and of length l(n) in the case of fixed length. | ||
70 | 2. Key k is generated by Gen(n) and a bit b <- {0,1} is | ||
71 | chosen uniformly at random (50/50). The (or rather a) ciphertext | ||
72 | c = Enc_k(m_b) as well as the security parameter n are then given to A. | ||
73 | 3. A answers by outputting a bit b'. | ||
74 | 4. The output of the experiment is defined 1 if b=b' and 0 otherwise. | ||
75 | |||
76 | |||
77 | Definition: A scheme Pi=(Gen,Enc,Dec) has *indistinguishable | ||
78 | encryptions in the presence of an eavesdropper* if there is a | ||
79 | negligible function negl(n) such that for all adversaries A | ||
80 | |||
81 | Pr[PrivK^eav_{A,Pi}(n) = 1] <= 1/2 + negl(n) | ||
82 | |||
83 | Remark: rather than having the adversary supply m0 and m1 they could | ||
84 | also be universally quantified. Randomizing over m0 and m1 would lead | ||
85 | to a weaker (and unreasonable) definition though. | ||
86 | |||
87 | |||
88 | *Semantic security* proper: | ||
89 | |||
90 | One can show (see 3.2) that this definition is equivalent to other | ||
91 | ones that give even more power to the adversary. The most compelling | ||
92 | one is "semantic security" which assumes an arbitrary probability | ||
93 | distribution on the plaintexts and also partial information on the | ||
94 | plaintexts to be given to the adversary. | ||
95 | |||
96 | We remark that in general proofs of semantic security (in the sense of | ||
97 | the above definition) are constructive in that the negligible function | ||
98 | bounding the probability can be read off as an explicit term. From | ||
99 | this, one can --- possibly after optimizing the constructions used in | ||
100 | the proof --- read off concrete bounds for fixed security parameter n. | ||