CAS CS538: Cryptography. Spring 2023 Instructor: , Ran Canetti
February 22, 2023
Wednesday Feb 22
Discussion 4
Copyright By PowCoder代写 加微信 powcoder
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 1 An ensemble F = {Fλ}λ∈N where Fλ : {0, 1}λ × {0, 1}n(λ) → {0, 1}l(λ) is a pseudorandom function (PRF) if it is computable in polynomial time (i.e., there exists apolytime algorithm F such that F(k,x) = F|k|(k,x) for all k,x), and in addition 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) λλ
Construction 1 (The Goldreich-Goldwasser-Micali PRF construction) Let G : {0, 1}λ → {0, 1}2λ be a secure PRG, and let us denote by (G0(k),G1(k)) = G(k) the first and second n-bit halves of G(k). Let F = {Fλ : {0, 1}λ , {0, 1}n(λ) → {0, 1}λ }λ∈N denote the ensemble of family of functions defined by:
Fλ(k, x) = Gxn(λ) (Gxn(λ)−1 (...(Gx1 (k))...)) where x = x1 ...xn(λ) is the input in bits and k ∈ {0, 1}λ is the key.
Question 1 : The GGM construction was presented in class as a construction of an ensemble of function families, where the nth family consists of functions from {0,1}n to {0,1}n. We wish to construct pseudorandom function family ensembles where the domain of the function is {0,1}∗. (That is, the adversary can ask queries of any length; but note that since the adversary is polynomial, it can only ask queries of polynomial length.)
(a) The GGM construction as as defined in class is actually well defined for inputs of any length. Show that when the domain of the functions is {0, 1}≤n(λ) the GGM construction is no longer secure.
(b) Show how to construct ensembles of secure pseudorandom function families with domain {0, 1}≤n(λ) and range {0, 1}n(λ).
(a) We construct an adversary Aλ as following: Aλ sends an arbitrary x1 ∈ {0, 1}