CAS CS538: Cryptography. Spring 2023
February 15, 2023
Due: 10pm Mon Feb 20
Homework 3
Question 1 (0 points): Read the definitions below. Make sure you understand them: what they define, and why they are formulated as they are. If you don’t understand, ask your fellow students, post a question on Piazza, or, if all else fails, ask Jessica, Luowen, or Ran. (You can also do the above in the reverse order.)
Distributions and ensembles. We define distributions by way of specifying the algorithm that takes an input that is uniformly drawn from some domain and generates a sample from the distribution. More specifically a distribution D is an algorithm (say, a Boolean circuit). To sample an element from D. one uniformly draws a string r ∈ {0,1}l, where l is the number of input wires in D, and returns the string d = D(r). We use the
shorthand d ←$ D to denote this process. Note that by this convention, the domain of a distribution is always contained in {0, 1}∗.
Recall the definition of statistical distance between distributions:
Definition 1 Let D1 and D2 be two distributions. 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)= 1 |Prob[d←D1 :d=x]−Prob[d←D2 :d=x]|.
2 x∈{0,1}∗
Equivalently, SD(D1,D2) is the maximum, over all (not necessarily efficient) algorithms A, of
|Prob[d←$ D1 :A(d)=1]−Prob[d←$ D2 :A(d)=1]|.
The (non-asymptotic) computational distance between distributions is defined analogously:
Definition 2 The computational distance between distributions D1 and D2 with respect to a class T of algorithms is the maximum, over all algorithms A ∈ T , of
|Prob[d←$ D1 :A(d)=1]−Prob[d←$ D2 :A(d)=1]|.
Towards an asymptotic notion of computational distance and indistinguishability, we first define distribution
ensembles:
Definition 3 A distribution ensemble is an infinite sequence of distributions D = {Dλ}λıλN , where each Dλ is a distribution. D has randomness complexity l(λ) if Dλ has l(λ) input wires. Ensemble D is effectively samplable if the size of Dλ (as a Boolean circuit) is polynomial in λ. If there exists a polytime algorithms D such that D(r) = Dλ(r) for all λ and all r ∈ {0,1}l(λ), then D is efficiently samplable. In this case we say that D is generated by D.
Next we define the statistical distance between distribution ensembles and statistically indistinguishable en- sembles:
Definition 4 Distribution ensembles X = {Xλ}λ∈N and Y = {Yλ}λ∈N have statistical distance at most δ(λ) if SD(Xλ,Yλ) < δ(λ) for all λ, or in other words for any (not necessarily feasible) distinguishing algorithm A = {Aλ}λ∈N , and for all large enough λ ∈ N, we have
Prob[s ←$ Xλ, Aλ(s) = 1] − Prob[s ←$ Yλ, Aλ(s) = 1] < δ(λ).
If δ(λ) is a negligible function then we say that ensembles X,Y are statistically indistinguishable, denoted X ≈s Y. Next we move on to define computational distance between ensembles, and computational indistinguishability:
Programming Help, Add QQ: 749389476
Definition 5 Distribution ensembles X = {Xλ}λ∈N and Y = {Yλ}λ∈N have computational distance at most δ(λ) if for any feasible distinguishing algorithm A = {Aλ}λ∈N , and for all large enough λ ∈ N, we have
Prob[s ←$ Xλ, Aλ(s) = 1] − Prob[s ←$ Yλ, Aλ(s) = 1] < δ(λ).
If δ(λ) is a negligible function then we say that ensembles X,Y are computationally indistinguishable, denoted
The uniform distribution ensemble over strings of length l(λ) is Ul() = {Uλ}λ∈N, where Uλ is the uniform distribution over {0, 1}l(λ). (More specifically, Uλ is the circuit with l(λ) input wires and no gates, i.e. each input wire is also an output wire.)
A function g : {0, 1}∗ → {0, 1}∗ has stretch (or, expansion factor) t() if its output is longer than its input by a factor of t(), namely if for all λ ∈ N and all x ∈ {0, 1}λ we have that g(x) ∈ {0, 1}λ+t(λ).
Definition 6 A polytime computable function G : {0, 1}∗ → {0, 1}∗ with stretch t(λ) is a pseudorandom generator if G ≈c Ul(), where l(λ) = λ + t(λ), and G is the distribution ensemble generated by G.
Hard-core predicates. In class we defined hard-core predicates as predicates that cannot be distinguished from random even given the function value. That is:
Definition 7 Let f : {0, 1}∗ → {0, 1}∗. An efficiently computable function h : {0, 1}∗ → {0, 1} is a hard core predicate for function f if:
{x ←$ {0, 1}λ : f(x), h(x)}λ∈N ≈c {x ←$ {0, 1}λ, b ←$ {0, 1} : f(x), b}λ∈N
(Here the left hand side ensemble samples x uniformly from {0,1}λ and then outputs the pair f(x),h(x). The
right hand side ensemble samples x uniformly from {0,1}λ and a random by b, and outputs f(x),b.)
An alternative and equivalent formulation defines hard-core predicates as predicates that are hard to predict
even given the function value:
Definition 8 An efficiently computable function h : {0, 1}∗ → {0, 1} is a hard core predicate for function f : {0,1}∗ → {0,1}∗ if for any feasible adversary {Aλ}λ∈N there is a negligible function ν such that for all large enough λ we have
Prob[x←$ {0,1}λ,Aλ(f(x))=h(x)]≤1/2+ν(λ).
Semantically secure encryption. Next we define semantically secure encryption, in asymptotic notation. To accommodate the fact that the domain of keys would naturally depend on the security parameter, we treat the process of generating keys as a third algorithm, called the key generation algorithm (Gen).
For simplicity we restrict ourselves to the case where the message domain M does not depend on the security parameter. (The definition extends naturally to the case where the message domain is an ensemble {Mλ}λ∈N where Mλ is the message domain of the scheme with security parameter λ.)
We first consider the case of one-time encryption, namely the case where the key is used only once, to encrypt a single message.
Definition 9 A triple of algorithms (Gen,Enc,Dec) is a one-time semantically secure encryption scheme with respect to message domain M if:
Correctness: For any λ ∈ N and for any m ∈ M we have Prob[k ←$ Gen(1λ) : Dec(k, Enc(k, m)) = m] = 1. Secrecy: There is a negligible function ν(λ) such that for any two messages m1,m2 ∈ M and any feasible
adversary A = {Aλ}λ∈N we have:
Prob[b←$ {0,1}; k←$ Gen(1λ); c←$ Enc(k,mb) : Aλ(c)=b]<21+ν(λ).
Programming Help
Next we extend the definition to the case where the encryption algorithm is used to encrypt multiple messages with a single key. Here we allow the encryption algorithm to be stateful, or in other words to update the key at each encryption step.
We first consider the case where the sequence of messages to be encrypted is fixed in advance. This case is usually known as security against known plaintext attacks (KPA):
Definition 10 A triple of algorithms (Gen,Enc,Dec) is a stateful t-time semantically secure encryption scheme against known plaintext attacks (t-SS-KPA) with respect to message domain M if:
Correctness: For any λ ∈ N and for any sequence of t messages m1 , …, mt ∈ M t we have
k1 ←$ Gen(1λ);
(c1, k2) ← Enc(k1, m1); (c2, k3) ← Enc(k2, m2); …; (ct, kt+1) ← Enc(kt, mt) : ∀i, Dec(k1, ci) = mi
Secrecy: There is a negligible function ν(λ) such that for any two sequences of messages m01, …, m0t , m1, …, m1t ∈ M2t, any feasible adversary A = {Aλ}λ∈N, and all large enough λ we have:
b←$ {0,1};k1←$ Gen(1λ);
ciphertexts seen so far. This case is usually known as security against chosen plaintext attacks (CPA): Definition 11 A triple of algorithms (Gen,Enc,Dec) is a stateful t-time semantically secure encryption scheme
against chosen plaintext attacks (t-SS-CPA) with respect to message domain M if:
Correctness: For any feasible adversary A = {Aλ}λ∈N and any λ ∈ N we have
Next we consider the case where each next message to be encrypted is chosen by the adversary, based on the
(c1, k2) ← Enc(k1, mb1); (c2, k3) ← Enc(k2, mb2); …; (ct, kt+1) ← Enc(kt, mbt ) : Aλ(c1,…,ct)=b
Prob
k1 ← Gen(1λ); m1 ← Aλ : (k2, c1) ← Enc(k1, m1);
m2 ←Aλ(c1);…;mt ←Aλ(c1,…,ct−1);(ct;kt+1)←Enc(kt,mt) : ∀i,ifmi∈Mthen Dec(k1,ci)=mi
Secrecy: There is a negligible function ν(λ) such that for any feasible adversary A = {Aλ}λ∈N and all large enough λ we have:
b ← {0,1} ; k1 ← Gen(1λ) ;(m01,m1) ← Aλ ; (k2,c1) ← Enc(k1,mb1); 1
Prob 0 1 0 1 b < +ν(λ). (m2, m2) ← Aλ(c1); ...; (mt , mt ) ← Aλ(c1, ..., ct−1); (ct; kt+1) ← Enc(kt, mt ) 2
: Aλ(c1,...,ct)=b
Question 2 (30 points): The advantage of distinguishing between distributions D1,D2 with respect class T of algorithms is defined as the maximum over all algorithms A ∈ T of
|Prob[b←$ {0,1}; d←$ Db : A(d)=b]−21|.
Show that the computational distance between D1 and D2 with respect to class T is ε if and only if the
advantage of distinguishing between D1,D2 with respect to class T is ε/2.
(Direction: Each side of the “if and only if” is proven via a reduction that uses an adversary that breaks one formulation of the definition and builds an adversary that breaks the other formulation. A full proof would describe each one of the two reductions, and then demonstrate its validity by demonstrating the success probability of the constructed adversary. You can assume that whenever the given adversary is in class T, the constructed adversary is also in class T .)
Question 3 (80 points):
Let X = {Xλ}λ∈N and Y = {Yλ}λ∈N be two effectively generatable computationally indistinguishable distribution ensembles, namely X ≈c Y. Show that X2 ≈c Y2, where D2 = {Dλ2}λ∈N and Dλ2 is the distribution where a single sample consists of two independently drawn samples from Dλ. (Hint: Use a hybrid argument. What would be the hybrid distribution?)
Does the same hold even when X , Y are not effectively samplable? either argue why or show a counter example. What about the case where one out of X , Y is effectively samplable?
3.1 (20 points)
*3.2 (20 points): **3.3 (40 points):
Question 4 (30 points):
4.1 (15 points) Show that if G is a length-doubling pseudorandom generator then G is also a one-way function.
*4.2 (15 points) Is this implication necessarily true when G is a pseudorandom generator with stretch 1? Either prove
or show a counter example.
Question 5 (20 points):
5.1 (10 points) Let f : {0, 1}∗ → {0, 1}∗ be an efficiently computable injective (i.e., one to one) function. Show that if f has a hard-core predicate as in Definition7 then f is one way.
5.2 (10 points) Is this implication necessarily true when G not injective? Either prove or show a counter example.
Question 6 (60 points): For each one of the following statements, either provide a short proof or a counter example demonstrating its fallacy:
Let X (0), X (1) be efficiently generatable probability ensembles with computational distance at most 1 . Show that Y (0) ≈c Y (1) , where Y (b) = {Y (b) }λ∈N and Y (b) is the following distribution: A sample
y from Y(b) is an λ-tuple y = y1,...,yλ, where yi is an independently drawn sample from X(bi), and
λλ b1, ..., bλ are uniformly from {0, 1}λ subject to b1 ⊕ ... ⊕ bλ = b.
程序代写 CS代考 加微信: cstutorcs
6.1 (15 points) For any t > 1, any stateful t-SS-KPA encryption scheme (as in Definition 10) is also (t + 1)-SS-KPA. 6.2 (15 points) For any t > 1, any stateful t-SS-KPA encryption scheme satisfies the correctness property of t-SS-CPA
encryption (Definition 11).
*6.3 (20 points) For any t > 1, any stateful t-SS-KPA encryption scheme is also t-SS-CPA.