CAS CS538: Cryptography. Spring 2023
February 23, 2023
Due: 10pm Mon Feb 27
Homework 4
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.)
First we formulate semantically security against chosen plaintext attacks (SS-CPA) in the context of stateless encryption schemes:
Definition 1 A triple of algorithms (Gen,Enc,Dec) is a stateless 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, any m ∈ M, and any λ ∈ N we have Prob[k ←$ Gen(1λ) c ←$ Enc(k, m) : Dec(k, c) = m] = 1.
Secrecy: There is a negligible function ν(λ) such that for any feasible adversary A = {Aλ}λ∈N and all large enough λ we have:
Pseudorandom functions and permutations. Informally, a family of functions with domain D and range R is is pseudorandom if: (a) it is computable in polynomial time (i.e., there exists a polytime algorithm F that given k and x ∈ D evaluates the kth function in the family on input x), and (b) no feasible adversary can distinguish, when given oracle access to an unknown function, between the case where the function was drawn at random from the family, and the case where the function was drawn randomly from all functions with domain D and range R.
We use the following notation: For a function F(·) and an algorithm A, we let AF(·) denote the output of algorithm A after an interaction with F(·) where A repeatedly provides an input value x of its choice to F(·), and is provided with F (x). In this case we also say that A has oracle access to F (·).
The definition below formulates an asymptotic version of PRFs, where a PRF is an ensemble of families, one family for each value of the security parameter λ. For simplicity we concentrate on the case where the domain of keys is {0,1}λ, and the domain and range of all the functions in the family are the full set of strings of some length. We let Fn,l = {f : {0,1}n → {0,1}l} be the set of all functions from n-bit strings to l-bit strings.
Definition 2 An ensemble F = {Fλ}λ∈N of function families where Fλ : {0, 1}λ × {0, 1}n(λ) → {0, 1}l(λ) is a pseudorandom function (PRF) if: (a) it is computable in polynomial time (i.e., there exists a polytime algorithm F such that F (k, x) = F|k|(k, x) for all k, x), and (b) there exists a negligible function ν(λ) such that for all feasible adversaries A = {Aλ}λ∈N and all large enough λ we have
Prob[k ←$ {0, 1}λ : AF (k,·) = 1] − Prob[R ←$ Fn(λ),l(λ) : AR(·) = 1] < ν(λ). (1) λλ
Next we define pseudorandom families of permutations (PRPs). Informally, a family of functions with domain and range D is a pseudorandom permutation family if (a) it is computable in polynomial time, (b) each function in the family is injective and onto, and (c) no feasible adversary can distinguish, when given oracle access to an unknown function, between the case where the function was drawn at random from the family, and the case where the function was drawn randomly from all permutations on D (i.e. all injective functions from D onto itself).
As in the case of PRFs, we formulate an asymptotic version of PRPs, where a PRP is an ensemble of families,
b ←$ {0,1} ; k ←$ Gen(1λ) ;(m01,m1) ← Aλ ; c1 ←$ Enc(k,mb1); $
(m02,m12)←Aλ(c1);...;(m0t,m1t)←Aλ(c1,...,ct−1);ct ←Enc(k,mbt) : Aλ(c1,...,ct)=b
one family for each value of the security parameter λ. We let the domain of keys is {0,1}λ, and the domain of all n perm n
the permutations in the family is the full set of strings of some length. We let Pn = {f : {0, 1} → {0, 1} } be the set of all permutations on the set of n-bit strings.
Programming Help, Add QQ: 749389476
Definition 3 An ensemble P = {Pλ }λ∈N of function families where Pλ : {0, 1}λ × {0, 1}n(λ) → {0, 1}n(λ) is a pseudorandom permutation (PRP) if: (a) for each k ∈ {0, 1}λ the function Pλ(k, ·) is a permutation on {0, 1}n(λ), (b) there exists a polytime algorithm F such that F (k, x) = F|k|(k, x) for all k, x), and (c) there exists a negligible function ν(λ) such that for all feasible adversaries A = {Aλ}λ∈N and all large enough λ we have
Prob[k←$ {0,1}λ :AP(k,·) =1]−Prob[R←$ Pn(λ) :AR(·) =1]<ν(λ). (2) λλ
Finally we define strong pseudorandom families of permutations (SPRPs). Informally, a strong PRP is a PRP where (a) the family is close under inverse, i.e. for each permutation in the family, the inverse permutation is also in the family, and (b) no feasible adversary can distinguish, when given oracle access to two unknown functions, between the case where one function was drawn at random from the family and the other is its inverse, and the case where one function was drawn randomly from all permutations on D (i.e. all injective functions from D onto itself), and the other one is its inverse.
Definition 4 An ensemble P = {Pλ }λ∈N of function families where Pλ : {0, 1}λ × {0, 1}n(λ) → {0, 1}n(λ) is a strong pseudorandom permutation (SPRP) if: (a) it is a PRP, (b) it is closed under inverse: for all λ, if p ∈ Pλ then p−1 ∈ Pλ, (c) there exists a negligible function ν(λ) such that for all feasible adversaries A = {Aλ}λ∈N and all large enough λ we have
$ λ P (k,·),P (k,·)−1 $ R(·),R−1 (·)
Prob[k←{0,1} :Aλ =1]−Prob[R←Pn(λ) :Aλ =1]<ν(λ). (3)
Question 2 (35 points):
1. (20 points) Your coworker has proposed to increase the security of your company’s SS-CPA stateless scheme (Gen,Enc,Dec) by double-encrypting each message. That is, assume your company’s scheme has message space Mλ = {0,1}≤λ and the ciphertext lenth is twice the length of the message. Then the proposal is to use the scheme (Gen′, Enc′, Dec′), where the key generation is unchanged (i.e., Gen′ = Gen), Enc′(k, m) = Enc(k, Enc(k, m)), and Dec′(k, c) = Dec(k, Dec(k, c)). To compensate for the growth of the ciphertext, your coworker proposes to reduce the message space of the new scheme to M′ = {0,1}λ/2. However, management remains unconvinced that the new scheme is secure and your coworker has forgotten his crypto class. Can you help them show that the new scheme at least does not harm security, i.e. that it is t-SS-CPA secure, assuming that the original scheme is?
2. (20 points) Management is happy about your proof and has decided to apply the above transformation to all of the company’s stateless encryption schemes, including the old ones that are only SS-KPA secure. Can you advise management if this is a smart move? i.e., can you assert whether applying the above transform to any stateless encryption scheme that is t-SS-KPA secure will result in a scheme that is still t-SS-KPA secure?
3. (10 points) Management is so excited that it wants to apply the above transformation even to schemes that are stateful (but still SS-CPA secure). Can you advise management if this is a smart move? i.e., can you assert whether applying the above transform to any stateful encryption scheme that is tSS-CPA secure will result in a scheme that is still t-SS-CPA secure?
浙大学霸代写 加微信 cstutorcs
Question 4 (25 points):
This morning, your coworker decided to implement the stateless encryption scheme based on PRFs that they learned about in their crypto course. But since the course was a while back, they didnt remember exactly how the scheme went. They ended up with the following candidates. Can you help your coworker, by picking one of these candidates and proving that it is corect and t-SS-CPA secure for any t(λ) that is polynomial in λ? In all of these schemes, the key k and the encryption randomness r are chosen at random from {0,1}λ, the message space is M = {0, 1}λ , F is a PRF with keyspace, domain and range {0, 1}λ , and ⊕ denotes bitwise exclusive or.
• Enc(k,m)=(r,F(r,k)⊕m)
• Enc(k, m) = (r, F (m, (k, r)) (here the domain of F is {0, 1}2λ)
• Enc(k, m) = (r, F ((k, r)(r ⊕ m) (here the keyspace of F is {0, 1}2λ) • Enc(k,m)=(r,F(k,r)⊕r⊕m)
• Enc(k,m)=(r,F(k,k⊕r)⊕m)
Question 5 (20 points):
You are given two candidate PRPs, P and P′, each with keyspace {0,1}λ and over the domain {0,1}λ. You know for sure that both P and P′ implement permutation families, i.e. for each k ∈ {0,1}λ it holds that both P(k,·) and P′(k,·) are permutations on {0,1}λ, but you dont know for sure whether they are PRPs. Construct a permutation family Q over {0,1}λ such that Q is an PRP as long as at last one out of P and P′ is an PRP.
Question 6 (40 points): A family of functions H = {hk : {0, 1}λ → {0, 1}m}k∈{0,1}a is called pairwise indepen- dent if for any α,β ∈ {0,1}λ, α ̸= β, Prob[k ← {0,1}a : hk(α) = hk(β)] = 1/2m. (That is, the probability that
two fixed points in the domain collide under hk is exactly the same as if hk were a truly random function from {0,1}λ to {0,1}m.) There are many combinatorial constructions of pairwise independent functions families with relatively short keys.
1. [20 points] Show that the family {hA(x) = Ax}A∈Am×λ , where Aλ×m is the set of λ by m binary matrices, and the arithmetic is done in GF2, is universal hash. (Arithmetic in GF2 means standard integer arithmetic, when the result of each operation is reduced modulo 2. Recall that integer arithmetic includes addition and multiplication, no division.)
2. [20 points] Show how to modify the GGM construction of pseudorandom function families so that each evaluation of the function on inputs in {0, 1}λ will involve only log2 λ applications of the underlying length- doubling pseudorandom generator.
Direction: Incorporate a description of a function from a pairwise independent family in the key of the PRF. How should the function be used? What should be the domain and range of the function?
Question 7 (20 points):
1. [10 points] Show that if there exists a pseudorandom function family F = {Fλ}λ∈N, where the family Fλ
consists of functions from {0, 1}λ to {0, 1} then there exist one way functions.
2. [10 points] Does the implication still hold if the family Fλ consists of functions from {0,1} to {0,1}λ?
Programming Help