CAS CS538: Cryptography. Spring 2023
January 31, 2023
Due: 10pm Mon Feb 6
Homework 2
Recall the definitions:
Definition 1 A function ν : N → R+ is negligible if for all large enough n we have ν(n) < 1/nc. (By “for all
large enough n...” we mean “for any any c > 0 there exists an nc such that for all n > nc… ”.)
Definition 2 A function f : {0,1}∗ → {0,1}∗ is one way if for any feasible adversary A={An}n∈N and for all
large enough n ∈ N we have
Prob[x ←$ {0, 1}n; x′ ← An(f(x)) : f(x′) = f(x)] < ν(n) where ν() is a negligible function.
Definition 3 A function f : {0, 1}∗ → {0, 1}∗ is weakly one way if there exists a constant c > 0 such that for any A = {An}n∈N and for all large enough n ∈ N we have
Prob[x←$ {0,1}n;x′ ←An(f(x)):f(x′)=f(x)]<1−n−c.
Question 1 (20 ): For each one of the following statements, either provide a proof, or show a counter-example:
1. (15 pts) 2. (15 pts)
3. (15 pts)
4. (15 pts) 5. (15 pts)
6. (15 pts)
Every encryption scheme (Enc, Dec) that has perfect correctness and perfect Shannon secrecy perfectly hides all bits of the key.
If there exist one way functions then there exist one way functions where the first half of the bits of the input are copied to the output. (In other words, if there exist one way functions then there exist one way functions that are first-half-preserving, where a function f : {0,1}∗ → {0,1}∗ is first-half- preserving if for any x = x1,x2 where |x1| = |x2| we have that f(x) = y1,y2 where y1 = x1. Here and throughout the class, we denote the number of bits in a string x ∈ {0, 1}∗ by |x|.)
In every encryption scheme (Enc,Dec) with message space {0,1}n, and that has perfect correctness and perfect Shannon secrecy, the ciphertext of any given message is uniformly distributed string in {0,1}m forsomem≥n.
If there exist one way functions then there exist one way functions that are length preserving. (A function f : {0, 1}∗ → {0, 1}∗ is length preserving if |f (x)| = |x| for all x ∈ {0, 1}∗ .)
In every encryption scheme (Enc,Dec) that has perfect correctness and perfect Shannon secrecy, and where the message space is {0,1}n, the ciphertext of any given message is uniformly distributed string in {0, 1}m for some m ≥ n, where the probability is taken over the choice of the key. (Here we restrict attention to deterministic encryption schemes, namely encryption schemes where the ciphertext is a deterministic function of the message and the key.)
In every encryption scheme (Enc,Dec) that has perfect correctness and perfect Shannon secrecy, the ciphertext of any given message is uniformly distributed string in C, where C is the domain of possible ciphertexts. (Here too we restrict attention to deterministic encryption schemes, namely encryption schemes where the ciphertext is a deterministic function of the message and the key.)
Question 2 (30%): Let D1 and D2 be two distributions over the same domain X. The statistical distance (or, total variation distance) between distributions D1 and D2 is denoted SD(D1,D2) and is defined as follows:
SD(D1, D2) = 21 |Probd←D1 [d = x] − Probd←D2 [d = x]| x∈X
1. (15 pts) Let D1 and D2 be two distributions over the same domain X. Show that if SD(D1, D2) = δ then there is a (not necessarily efficient) algorithm A such that |Probd←D1 [A(d) = 1] − Probd←D2 [A(d) = 1]| ≥ δ.
CS Help, Email: tutorcs@163.com
2. (15 pts)
3. (*15 pts)
Let D1 and D2 be two distributions over the same domain X. Show that if there exists a (not necessarily efficient) algorithm A such that t |Probd←D1 [A(d) = 1] − Probd←D2 [A(d) = 1]| ≥ δ then SD(D1, D2) ≥ δ.
Say that an encryption scheme (Enc, Dec) with message domain M and key domain K has ε-Shannon secrecy if for every two messages m1,m2 ∈ M we have SD(Enc(m1),Enc(m2)) ≤ ε. Here Enc(m) denotes the probability distribution that’s generated by picking a key k uniformly at random from K and evaluating Enc(k, m).
For any ε < 1/2, show an encryption scheme with ε-Shannon secrecy, and where |K| ≤ (1 − ε)|M|). (Hint: Start off with a standard One-Time-Pad and remove some of the keys in a way that allows you to prove that the scheme still has ε-Shannon secrecy.)
Showthatifanencryptionscheme(Enc,Dec)hasε-Shannonsecrecythen|K|≥(1−ε)|M|.
gn is a generator of the group Zp∗ . (That is, the nth pair in the sequence is a prime pn of n bits, and a
4. (**30pts)
Question 3 (*30 pts): Consider the sequence P = {(pn;gn)}n∈N such that 2n < pn < 2n+1 is a prime and
generator gn of Zp∗ .) n
The exponentiation function EXP : Z∗ → Z∗ is defined as EXP(x) = gx mod p , where n = |x|. pn pn n n
Recall that in class we said that the modular exponentiation function is one way, assuming that computing discrete logarithms is hard. (Note that EXP is defined slightly differently than the modular exponentiation function described in class. This is so since here we are interested in computing discrete logarithms modulo a specific fixed generator gn, rather than computing discrete logarithms with respect to a random basis that’s given in the input. However, the difference is not substantial.)
Prove that if EXP is weakly one way then it is also one way. That is, for each n, show how to transform any algorithm An that inverts EXP on a 1/nc-fraction of the elements in Zp∗ into an algorithm A′n that runs
in time that’s only polynomially more than An, and such that that A′n inverts EXP on 1 − ν(n)-fraction of the elements in Z∗ for some negligible function ν(n).
Hint: It will be easier to think about constructing a randomized A′n that will invert EXP on all elements
in Z∗ with probability 1 − 1/2n over the random choices of A′ . The fact that ga · gb ≡ g(a+b) may come pn np
Code Help