Assignment #2 Due date: Wednesday, April 28, 2021, 11:59pm Course: Introduction to Cryptography Quarter: Spring 2021 Instructor: Prabhanjan Ananth Instructions • This assignment is worth 100 points. •...

Assignment #2
Due date: Wednesday, April 28, 2021, 11:59pm
Course: Introduction to Cryptography
Quarter: Spring 2021
Instructor: Prabhanjan Ananth
Instructions
• This assignment is worth 100 points.
• Please read all the instructions very carefully.
• Submissions must be made on Gradescope. The enrollment code is on Slack.
• Make sure that the handwriting in your solutions is legible (using LATEX to typeset
your solutions is appreciated a lot!). Be precise and concise in your solutions. Explain
your solutions clearly and provide mathematical proofs wherever necessary.
• Write the solution to each problem on a separate page.
• If you don’t know how to solve a problem, write “I don’t know” and you get 20% of
the points.
• You are allowed to collaborate with at most two more students on these assignments.
However, everyone is expected is write up the solutions on their own and submit it
individually. Clearly state the names of all your collaborators.
• Do not use any theorem or lemma from the internet that was not taught in the class.
Use only the material covered in the class to solve these problems.
• More importantly, have fun solving these problems!
1
Free Hand
Problem 1 [10 points]
Are the following functions negligible or non-negligible? Justify your answer.
1. 51(=) = 5 (=) · =2 , for some constant 2 > 0 and some negligible function 5 (=)
2. 52(=) = =− log log =
Problem 2 [15 points]
Recall that two ensembles {-=}, {.=} where -= , .= ∈ {0, 1}?>;H(=) are computationally indistin-
guishable if for any efficient adversaryA, there exists a negligible function &(=) such that
|Pr[A(1= , G) = 1; G ← -=] − Pr[A(1= , H) = 1; H ← .=]| ≤ &(=)
Let 5 : {0, 1}∗ → {0, 1}∗ be a polynomial-time computable function. Show that if {-=}, {.=} are
computationally indistinguishable, then { 5 (-=)}, { 5 (.=)} are also computationally indistinguish-
able.
[Hint: Use reductions.]
Problem 3 [15 points]
If {-=}, {.=} are computationally indistinguishable, and {.=}, {/=} are computationally indis-
tinguishable, show that {-=}, {/=} are computationally indistinguishable.
Problem 4 [15 points]
Give examples of non-negligible functions 51(=) and 52(=) such that 51(=) · 52(=) is actually a
negligible function.
Problem 5 [25 points]
Let � : {0, 1}= → {0, 1}3= be a secure pseudorandom generator, prove that the following pseu-
dorandom generators are secure.
B, A ∈ {0, 1}= below are perfectly random strings. You can think of them as the seeds of the
PRG.
1. �1(B) : {0, 1}= → {0, 1}2= , �1(B) = �(B)[2=]. That is, �1(B) is obtained by dropping the last
= bits of �(B).
2. �2(A, B) : {0, 1}2= → {0, 1}6= , �2(A, B) = (�(A), �(B)).
Problem 6 [20 points]
1. Is the following function 5 : {0, 1}= → {0, 1}= a one-way function? ∀G ∈ {0, 1}= ,
5 (G) = G + 10 (mod 2=)1.
1Here G ∈ {0, 1}= is interpreted as a number between 0 and 2= − 1. For instance, 10 ≡ XXXXXXXXXX
2
2. Suppose 5 : {0, 1}= → {0, 1}= is a one-way function. Using 5 , can you construct another
function 5 ′ : {0, 1}= → {0, 1}=+1 such that 5 ′ is also a one-way function but not a secure
pseudorandom generator.
3
May 02, 2021

Submit New Assignment

Copy and Paste Your Assignment Here