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/Notes03.txt | 100 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+) create mode 100644 ss2017/cryptography/Notes03.txt (limited to 'ss2017/cryptography/Notes03.txt') 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 @@ + + +3 Semantic Security (KL3.1, KL3.2) +---------------------------------- + +In order to formally study secrecy of schemes that use shorter keys +one must somehow incorporate the computational power of an +adversary. One way of doing this is to use concrete bounds: + +A scheme is (t,epsilon)-secure if every adversary running for time t +succeeds in breaking the scheme (in the appropriate sense) with +probability at most epsilon. + +For example, if we use keys of bit length n and the only possible +attack is by trying out all keys (this happens e.g. with Vernam's +cipher) then assuming that 10^9 keys can be tried out every second +(1GHz) trying out 2^60 operations takes 35years thus several years +even with highly parallel computers. Thus, a 60bit key takes this time +to be broken with certainty, a 64 bit key takes this time to be broken +with probability 1/16 etc. Currently, one recommends key lengths of +128bit (128 *bits of security*) to make the success probability +negligible (e.g. lower than that of a meteor crashing into the device) +and to allow for future technological advances. + +Now, working with concrete runtimes and probabilities is difficult and +brittle because of its dependency on concrete hardware configuration, +programming language, implementation details, etc. As a result, one +uses instead an asymptotic approach where runtimes and probabilities +as well as sizes of keys and texts are functions of a *security +parameter* n. One then wants that the success probability of an +adversary whose runtime is polynomial in the security parameter is a +*negligible function* of the security parameter, i.e. smaller than n^k +for any k. + +Definition: A private-key encryption scheme is a tuple of +probabilistic polynomial-time algorithms (Gen,Enc,Dec) such that: + +1. Gen computes a key (in {0,1}^*) from the security parameter +(presented in unary, i.e. as 1...1 (n times)). We write this as k <- +Gen(n) or k <- Gen(1^n) to emphasize the unary notation. + +2. Enc_k(m) and Dec_k(c) are as before, except that m, c are +bitsequences (in {0,1}^*). In particular, we must have Dec_k(Enc_k(m))=m. + +A fixed-length private-key encryption scheme is defined analogously, +but there is a function l(n) fixing the length of plaintexts as a +function of the security parameter. Formally, when k is returned from +Gen(n) then Dec_k(m) is defined only for m of length exactly l(n). + +For example, the one-time pad can be cast into this framework. Given +the security parameter n, Gen generates a random bit sequence of +length n. One has l(n)=n and Enc_k(m) = m+k etc. + + + +Indistinguishability in the presence of an eavesdropper +- - - - - - - - - - - - - - - - - - - - - - - - - - - - + +We now want to adapt the notion of perfect secrecy from above to the +asymptotic framework. An adversary thus also gets the security +parameter n and its runtime must be bounded by a polynomial in n. It +is allowed to use randomization (has access to random bits). + +Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment +PrivK^eav_{A,Pi}(n) is now defined as follows: + + + 1. The adversary produces two messages m0, m1 of equal length + and of length l(n) in the case of fixed length. + 2. Key k is generated by Gen(n) and a bit b <- {0,1} is + chosen uniformly at random (50/50). The (or rather a) ciphertext + c = Enc_k(m_b) as well as the security parameter n are then given to A. + 3. A answers by outputting a bit b'. + 4. The output of the experiment is defined 1 if b=b' and 0 otherwise. + + +Definition: A scheme Pi=(Gen,Enc,Dec) has *indistinguishable +encryptions in the presence of an eavesdropper* if there is a +negligible function negl(n) such that for all adversaries A + + Pr[PrivK^eav_{A,Pi}(n) = 1] <= 1/2 + negl(n) + +Remark: rather than having the adversary supply m0 and m1 they could +also be universally quantified. Randomizing over m0 and m1 would lead +to a weaker (and unreasonable) definition though. + + +*Semantic security* proper: + +One can show (see 3.2) that this definition is equivalent to other +ones that give even more power to the adversary. The most compelling +one is "semantic security" which assumes an arbitrary probability +distribution on the plaintexts and also partial information on the +plaintexts to be given to the adversary. + +We remark that in general proofs of semantic security (in the sense of +the above definition) are constructive in that the negligible function +bounding the probability can be read off as an explicit term. From +this, one can --- possibly after optimizing the constructions used in +the proof --- read off concrete bounds for fixed security parameter n. -- cgit v1.2.3