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 @@
+5 Security against chosen plaintext attacks (KL3.5)
+---------------------------------------------------
+
+We now consider security of cryptosystems against stronger adversaries
+which may request the encryption of arbitrary plaintexts of their
+choice. There are some practical scenarios where this might occur,
+e.g. a smartcard which can be interacted with arbitrarily or by
+preparing some situation whose description will then be transmitted by
+the opposite party in encrpyted form.
+
+
+Given a scheme Pi=(Gen,Enc,Dec) and an adversary A the experiment
+PrivK^cpa_{A,Pi}(n) is now defined as follows:
+
+
+  1. Key k is generated by Gen(n)
+  2. The adversary A is given the security parameter n and the procedure
+     Enc_k as a black box (oracle access). After some interaction with
+     the oracle it then outputs two messages m0 and m1 from {0,1}^{l(n)}
+     (or of the same length in the case of variable length schemes).
+  3. A  bit b <- {0,1} is chosen uniformly at random (50/50). The
+     (or rather a) ciphertext  c = Enc_k(m_b) is given to A.
+  4. A continues to have oracle access to Enc_k and then 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 under a chosen plaintext attack* (is cpa-secure for short)
+if there is a negligible function negl(n) such that for all (pr.-polytime)
+adversaries A
+
+      Pr[PrivK^cpa_{A,Pi}(n) = 1] <= 1/2 + negl(n)
+
+There is also a "known plaintext version" where the adversary does not
+get full-blown oracle access to Enc_k but can merely request
+encryptions of a previously submitted list of plaintexts. The details
+of this are left to the reader.
+
+We first notice that no deterministic scheme can possibly be
+cpa-secure. Given c simply compute (using the oracle) c_0=Enc_k(m_0)
+and c_1=Enc_k(m_1) and return b' such that c_b'=c. Thus, any cpa-secure
+scheme must include a random element into the encryption. But naive
+ways of doing so will not be successful either. Suppose for example
+that Pi=(Gen,Enc,Dec,l) is a deterministic scheme, i.e. Enc_k( ) is a
+function. Design a new scheme Pi' as follows:
+
+For bitstrings u,v we let u || v stand for the concatenation of u and
+v. If w is a bitstring of even length 2n then we let w.1 and w.2 stand
+for its first and second halves.
+
+Gen' = Gen
+l'(n) = l(n)/2 /* w.l.o.g. l(n) is even */
+Enc'_k(m) = Enc_k(r || m) where r is a random bitstring
+             of length l(n)/2.
+Dec'_k(c) = Dec_k(c).1
+
+Clearly, Pi' has indistinguishable encryptions in the presence of an
+eavesdropper if Pi has, but Pi' does not in general withstand chosen
+plaintext attacks. Namely, consider that Enc_k(m)=G(k)+m as above. We
+then have Enc'_k(m) = G(k).1 + r || G(k).2 + m.  As a result, the
+adversary can take the first half of the received ciphertext c,
+request encryptions c_0 nd c_1 of m_0 and m_1 and determine b' so that
+c.1 = (c_b').1 .
+
+In order to achieve the desired security we need a *pseudorandom function*
+
+Definition: A pseudorandom function (PRF) is a binary function on bitstrings
+
+                F : {0,1}^* x {0,1}^* -> {0,1}^*
+
+with application F(k,x) written F_k(x) such that
+
+ 1) |k|=|x| implies |F_k(x)|=|k|=|x| (and F need not be defined on
+    arguments of different length)
+
+ 2) F is deterministic, polynomial-time computable
+
+ 3) For all probabilistic polynomial-time distinguishers D and all n
+    one has
+
+     | Pr[ D^{F_k()}(n)=1 ] - Pr[D^{f()}(n)=1] | = negl(n)
+
+    for some negligible function negl() and probabilities taken over
+    k and f(), see below.
+
+The distinguisher has access to an oracle, i.e. a subroutine of type
+{0,1}^n->{0,1}^n. In the experiment, first k:{0,1}^n is drawn
+uniformly at random and then a function f from {0,1}^n->{0,1}^n is
+drawn uniformly at random (from the 2^{n*2^n} many possibilities). The
+oracle is then instantiated with F_k() on the one hand and
+with f on the other. The probabilities for the distinguisher to output
+1 in either case should differ only negligibly.
+
+So, where a pseudorandom generator expands a size n key k to a size
+l(n) bitstring that looks random a pseudorandom function expands a
+size n key to a function F_k which could be written as a size n*2^n
+bitstring. Again, this "very large" object should look
+random. However, only a polynomial portion of it can be examined by
+the distinguisher. On the other hand, which portion that is is up to
+the distinguisher to decide and not priori fixed.
+
+We remark that one often uses variants of PRF where the size of
+argument x and results are functions of a security parameter other
+than the identity function. (The security parameter must then be
+supplied explicitly to F)
+
+Relationship between PRF and PRG:
+
+It is not hard to see that every PRF can serve as a PRG. Given k
+simply output the string F(k,0) || F(k,1) || F(k,2) || ... || F(k,N) for
+sufficiently large N and where e.g. 2 stands for the encoding of 2 as
+a length n bitstring. If a distinguisher could tell this from a random
+string one could easily use it to distinguish F_k from a random
+function. Surprisingly, the converse also holds, see (KL6.5). However,
+we still do not know whether PRG exist.  In practice, PRF are
+constructed using heuristic approaches.
+
+
+A CPA-secure cryptosystem from a PRF (KL3.6.2)
+- - - - - - - - - - - - - - - - - - - - - - - -
+
+Here is, how we use a PRF to construct a CPA-secure cryptosystem. Note
+that by our earlier observation the scheme itself must be randomised.
+
+
+Gen(n): return a random bitstring of length n as key.
+Enc_k(m): choose r:{0,1}^n uniformly at random and output the ciphertext
+            c := r || F_k(r)+m
+Dec_k(c): given c extract c.1=r and c.2=F_k(r)+m then return c.2+F_k(r)
+
+Notice that Dec_k(Enc_k(m)) = F(k,r)+F(k,r)+m = m
+
+Remark: A random element like r added to a piece of data is known as a
+*nonce*.
+
+Theorem: If F is a PRF then the above construction yields a fixed
+length (l(n)=n) CPA-secure cryptosystem.
+
+Proof: Let Pi stand for the scheme constructed above from F and
+l(n). Assume further, that A is an adversary against Pi. We construct
+from A a distinguisher D for the PRF F as follows:
+
+Given security parameter n and oracle access to a function h (which is
+instantiated as either F_k() or a truly random f()) the distinguisher
+begins by passing the security parameter n to the adversary A.
+
+Now, whenever the adversary queries its own oracle which it assumes to
+be of the form Enc_k() then the distinguisher chooses r:{0,1}^n at
+random and returns r || h(r)+m to A.
+
+When the adversary enters the second phase and outputs two messages
+m_0, m_1 to distinguish based on their encryptions the distinguisher
+then chooses a random bit b:{0,1} and r:{0,1}^n uniformly at random
+and returns r || h(r)+m_b to A. Further oracle queries from A are
+answered as before.
+
+When A eventually outputs a bit b' reply 1 if b=b' and 0 otherwise.
+Let us see what the adversary can do when h is a truly random
+function. Unlike in the "eavesdropper" case, A has a certain
+advantage: namely suppose it has already requested encryptions c_0 and
+c_1 of the messages m_0 and m_1 it then forwards (and it would be
+"wise" for A to do so). If it now happens by accident that
+c.1=c_0.1=c_1.1, i.e. the three random nonces used were all equal,
+then since the rest is deterministic, the adversary can pick b' such
+that c.2=c_{b'}.2 and be correct. Since, however, the adversary can
+only make polynomially many queries the likelihood for this to happen
+is negligible. If, however, the random nonce used in the preparation
+of c is different from all the ones used in oracle queries then c
+looks completely random to A and its success probability is exactly
+1/2. Summing up, if h is truly random then A's success probability is
+1/2+negl(n).
+
+If, on the other hand, h is F_k(), then let p be the success
+probability of the adversary A on our new cryptosystem. It is clear
+that our distinguisher will output 1 with probability p for we have
+used A according to the rules of the PrivK^cpa-experiment. Since F was
+assumed to be a PRF we thus know that |p-(1/2+negl(n))| is itself
+negligible. It then follows that p is bounded by 1/2 plus a negligible
+function.                                                      Q.E.D.
+
+
+Notice that this proof newly introduces negligible probabilities
+rather than (or in addition to) just move them around and thus gives
+further evidence as to why allowing negligible deviations from the
+ideal situation is reasonable.
+
+We also remark that the way the system was presented the length of the
+key equals that of the message. However, in the case of a CPA-secure
+system we can encrypt several messages with the same key without
+compromising security. We generalise this idea in the next chapter.
+
+Proposition: Let Pi=(Gen,Enc,Dec) be cpa-secure and define
+Pi'=(Gen,Enc',Dec') by Enc'_k(m1 || m2) = Enc_k(m1) || Enc_k(m2). Then
+Pi' is cpa-secure. Here m1, m2, as well as, c1,c2 are assumed to be of
+equal length.
+
+Proof: From a hypothetical cpa-adversary A' against Pi' we construct a
+cpa-adversary A against the original system Pi as follows:
+
+A runs A' and answers any oracle requests according to Pi'. E.g. if A'
+asks for an encryption of m1||m2 it requests encryptions c1 and c2 of
+m1, m2, respectively and then provides the answer c1||c2.
+
+When A' outputs the challenge m1^0||m2^0 vs m1^1||m2^1 A submits the
+challenge m2^0 vs m2^1 and receives a ciphertext c2 (which should be an
+encryption of m2^0 or m2^1). A then requests an encryption c1 of m1^0 and
+passes c1||c2 to A'.
+
+The answer bit b' supplied by A' is then output.
+
+Let p be the success probability of A'.
+
+If the secret bit b is equal to 0 then the
+success probability of A is p as well.
+
+