Introduction to Cryptography – Fall 2022

Homework 3

*Notes:*

- This homework assignment is for individual students. Discussion is allowed. But you have to form your own solution.
- Only typed reports (hand drawing okay for figures if necessary and legible) are allowed for homework submission.
- Write in a concise way.
- Submit it through the given link at Canvas as a
**PDF**file. If there are multiple files, compress all files into one zip file. Verify that the submission is successful.

- (10pts) Let’s consider a system where for security parameter n, running for 10
^{9}*n^{3}clock cycles can break an encryption scheme with probability 16*n^{10}*2^{-n}. If n=64, this probability is 1 (magic!) for 10^{9}*n^{3}=10^{9}*64^{3}clock cycles, requiring a running time*T*of about three days on a 1Ghz computer. Now a more powerful 8Ghz computer becomes available. But n is also doubled to 128 in the encryption scheme as well. Using the same running time*T*as before on the new computer, what is the probability for this system to break this current encryption scheme? Please clearly show how you arrive at the conclusion.

(Hint: First find out how much computation can be done in the given time on the new computer. Then you can see how that relates to the success probability.)

- (20pts) This exercise is about PRG. Let us look at a deterministic algorithm G that outputs a string
*w*of length*ℓ*(n), i.e.,*w*ϵ{0,1}^{ℓ}^{(n)}. However, overall the seeds*s,*when we check each string*w*bit by bit, we find that the bit is 1 by a 50.01% chance.

Is this G a PRG? First, specifically, design a statistical distinguisher D based on the above observation. And then calculate the difference of the results of using this D to test *w*’s and truly random strings respectively. Please give out the formulation and solution step by step with an adequate explanation.