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 @@
+4 Pseudorandomness (3.3)
+------------------------
+
+In order to arrive at cryptosystems with keys considerably shorter
+than messages it is natural to use a generator which from a truly
+random seed produces (deterministically!) a sequence of bits that
+looks random. Indeed, such generators are often used in the
+implementation of random in standard libraries e.g. for C or Java.
+
+The question is whether a so constructed cryptosystem might be while
+not perfectly secret still enjoy semantic security.  The answer is yes
+if the generator is a *pseudorandom generator*, PRG for short, in the
+following sense.
+
+Definition (pseudorandom generator): Let l(n) be a polynomial and G a
+deterministic polynomial time algorithm that for any bitstring s of
+length n outputs a bitstring G(s) of length l(n). We call G a
+*pseudorandom generator* with expansion l(n) if for any probabilistic
+polynomial time adversary D ("distinguisher") it holds that
+
+ | Pr[D(r)=1] - Pr[D(G(s))=1] |  = negl(n)
+
+for some negligible function negl(n) and for all n.  Here s and r are
+bitstrings of lengths n and l(n), respectively, chosen uniformly at
+random.
+
+We remark that if l(n)=n then G(s)=s is trivially a pseudorandom
+generator and if l(n)>n and G is any function sending length n
+bitstrings to length l(n) bitstrings will be vulnerable against
+distinguishers with exponential computing power. Simply let D
+enumerate all length n bitstrings s' and check for each of them
+whether its input equals G(s'). Return 1 if yes, 0 otherwise. When fed
+G(s) the distinguisher will output 1 with certainty and if fed a
+random string then it will output one with probability 2^{-(l(n)-n)}
+only. The difference between these probabilities is not negligible.
+
+In summary, pseudorandom strings are as good as truly random ones so
+long as they are used in a probabilistic polynomial time context and
+one accepts negligible probability of failure.
+
+Unfortunately, one does not know whether there exist PRG with l(n)>n
+at all, but it is generally believed that they do. At least, there do
+exist several such objects for which no (probabilistic, polynomial
+time) distinguisher is currently known despite a lot of research.
+
+
+Semantically secure cryptosystems from PRG (KL3.4.1)
+- - - - - - - - - - - - - - - - - - - - - - - - - - 
+
+Assuming that we have a PRG G with expansion factor l(n). We can use
+it in order to construct a semantically secure fixed-length encryption
+scheme for messages of length l(n) as follows:
+
+Gen(n): return a random bitstring of length n as key.
+Enc_k(m): return G(k)+m /* + = bitwise XOR */
+Dec_k(c): return G(k)+c
+
+Notice that Dec_k(Enc_k(m)) = G(k)+G(k)+m = m
+
+Theorem: If G is a PRG of expansion l then the above construction has
+indistinguishable encryptions in the presence of an eavesdropper.
+
+Proof: Let Pi stand for the scheme constructed above from G and
+l(n). Assume further, that A is an adversary against Pi. We construct
+from A a distinguisher D as follows:
+
+Given a string w (either random or of the form G(s)) the distinguisher
+begins by letting the assumed adversary A produce two messages m0 and
+m1. It then selects b:{0,1} at random and sends m_b + w to the adversary A.
+If A outputs b the distinguisher returns 1 and it returns
+0 otherwise. Let p be the success probability of A in the PrivK^eav
+experiment which must be shown to be 0.5+negl(n). If w is truly random
+then so is m_b+w and the chance that A finds out b is exactly 1/2. If,
+on the other hand, w is G(s) for random s, then this likelihood is
+p. The difference between the two, i.e. p-1/2 is negligible since G
+was assumed to be a PRG and as a result p=1/2+negl(n) as required.
+Q.E.D.
+