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 @@
+
+
+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.