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 109*n3 clock cycles can break an encryption scheme with probability 16*n10*2-n. If n=64, this probability is 1 (magic!) for 109*n3=109*643 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.
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
