Homework 4 – ENEE 456 / CMSC 456 / MATH 456 – S21
密码学作业代写 Due to that, consider a CPA-secure encryption scheme that replaces the PRF above with a truly random function. Describe the challenges
Problem 1 (3%) 密码学作业代写
1.(coding up a distinguisher)(2%)
(a)Write down the definitions of perfect secrecy, computational indistin- guishability and CPA-security. Write down the definitions of security for pseudodandom generators, pseudodandom functions and pseudo- random
(b)LetZp = 0, 1, . . . , p 1 where p is an n-bit You are given the family of functions
Fk = {f (k, x) : f (k, x) = 2021 · k + x2 + 2020 mod p} ,
where k ∈ Zp and x ∈ Zp. Sample a function f (k, x) from Fk by picking a k uniformly at random from Zp. Is f (k, x) a pseudorandom function? If not, write pseudocode for a distinguisher and submit the file. Your distinguisher should output 1 to indicate that the input is not a truly random function, and 0 otherwise. Then compute the probability that your C code will output 1 when input a truly random function f (over the choice of f ) and the probability that your pseudocode will output 1 when input the function f (k, x) (over the choice of k). Finally argue that f (k, x) is not a pseudorandom function. 密码学作业代写
2.(CPA-security with truly random functions) (1%) In class, we talked about a simple CPA-secure scheme that encrypts a message x as (r, Fk(r) x), where Fkis a pseudorandom function and where r, x, k and Fk(r) are all n-bits strings. However, as we know, there are no constructions of PRFs that strictly satisfy the PDF definition and in practice we use heuristic con- structions like AES.
Due to that, consider a CPA-secure encryption scheme that replaces the PRF above with a truly random function. Describe the challenges that are in- volved in using such a scheme.
Problem 2 (3%) 密码学作业代写
- (small-domain truly random functions) (2%) Exercise 3.9 from Katzand Lindell (Page 103, second edition).
- (concatenating pseudorandom functions) (1%) Exercise 3.10 from Katz and Lindell (Page 103, secondedition).