diff options
Diffstat (limited to 'ss2017/cryptography/Notes04.txt')
-rw-r--r-- | ss2017/cryptography/Notes04.txt | 78 |
1 files changed, 78 insertions, 0 deletions
diff --git a/ss2017/cryptography/Notes04.txt b/ss2017/cryptography/Notes04.txt new file mode 100644 index 0000000..cabf8f9 --- /dev/null +++ b/ss2017/cryptography/Notes04.txt | |||
@@ -0,0 +1,78 @@ | |||
1 | 4 Pseudorandomness (3.3) | ||
2 | ------------------------ | ||
3 | |||
4 | In order to arrive at cryptosystems with keys considerably shorter | ||
5 | than messages it is natural to use a generator which from a truly | ||
6 | random seed produces (deterministically!) a sequence of bits that | ||
7 | looks random. Indeed, such generators are often used in the | ||
8 | implementation of random in standard libraries e.g. for C or Java. | ||
9 | |||
10 | The question is whether a so constructed cryptosystem might be while | ||
11 | not perfectly secret still enjoy semantic security. The answer is yes | ||
12 | if the generator is a *pseudorandom generator*, PRG for short, in the | ||
13 | following sense. | ||
14 | |||
15 | Definition (pseudorandom generator): Let l(n) be a polynomial and G a | ||
16 | deterministic polynomial time algorithm that for any bitstring s of | ||
17 | length n outputs a bitstring G(s) of length l(n). We call G a | ||
18 | *pseudorandom generator* with expansion l(n) if for any probabilistic | ||
19 | polynomial time adversary D ("distinguisher") it holds that | ||
20 | |||
21 | | Pr[D(r)=1] - Pr[D(G(s))=1] | = negl(n) | ||
22 | |||
23 | for some negligible function negl(n) and for all n. Here s and r are | ||
24 | bitstrings of lengths n and l(n), respectively, chosen uniformly at | ||
25 | random. | ||
26 | |||
27 | We remark that if l(n)=n then G(s)=s is trivially a pseudorandom | ||
28 | generator and if l(n)>n and G is any function sending length n | ||
29 | bitstrings to length l(n) bitstrings will be vulnerable against | ||
30 | distinguishers with exponential computing power. Simply let D | ||
31 | enumerate all length n bitstrings s' and check for each of them | ||
32 | whether its input equals G(s'). Return 1 if yes, 0 otherwise. When fed | ||
33 | G(s) the distinguisher will output 1 with certainty and if fed a | ||
34 | random string then it will output one with probability 2^{-(l(n)-n)} | ||
35 | only. The difference between these probabilities is not negligible. | ||
36 | |||
37 | In summary, pseudorandom strings are as good as truly random ones so | ||
38 | long as they are used in a probabilistic polynomial time context and | ||
39 | one accepts negligible probability of failure. | ||
40 | |||
41 | Unfortunately, one does not know whether there exist PRG with l(n)>n | ||
42 | at all, but it is generally believed that they do. At least, there do | ||
43 | exist several such objects for which no (probabilistic, polynomial | ||
44 | time) distinguisher is currently known despite a lot of research. | ||
45 | |||
46 | |||
47 | Semantically secure cryptosystems from PRG (KL3.4.1) | ||
48 | - - - - - - - - - - - - - - - - - - - - - - - - - - | ||
49 | |||
50 | Assuming that we have a PRG G with expansion factor l(n). We can use | ||
51 | it in order to construct a semantically secure fixed-length encryption | ||
52 | scheme for messages of length l(n) as follows: | ||
53 | |||
54 | Gen(n): return a random bitstring of length n as key. | ||
55 | Enc_k(m): return G(k)+m /* + = bitwise XOR */ | ||
56 | Dec_k(c): return G(k)+c | ||
57 | |||
58 | Notice that Dec_k(Enc_k(m)) = G(k)+G(k)+m = m | ||
59 | |||
60 | Theorem: If G is a PRG of expansion l then the above construction has | ||
61 | indistinguishable encryptions in the presence of an eavesdropper. | ||
62 | |||
63 | Proof: Let Pi stand for the scheme constructed above from G and | ||
64 | l(n). Assume further, that A is an adversary against Pi. We construct | ||
65 | from A a distinguisher D as follows: | ||
66 | |||
67 | Given a string w (either random or of the form G(s)) the distinguisher | ||
68 | begins by letting the assumed adversary A produce two messages m0 and | ||
69 | m1. It then selects b:{0,1} at random and sends m_b + w to the adversary A. | ||
70 | If A outputs b the distinguisher returns 1 and it returns | ||
71 | 0 otherwise. Let p be the success probability of A in the PrivK^eav | ||
72 | experiment which must be shown to be 0.5+negl(n). If w is truly random | ||
73 | then so is m_b+w and the chance that A finds out b is exactly 1/2. If, | ||
74 | on the other hand, w is G(s) for random s, then this likelihood is | ||
75 | p. The difference between the two, i.e. p-1/2 is negligible since G | ||
76 | was assumed to be a PRG and as a result p=1/2+negl(n) as required. | ||
77 | Q.E.D. | ||
78 | |||