cryptography

Homework 3: Complexity & Security

Purpose

This homework is designed to do several things:

• The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.

• Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.

• Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.

Instructions

Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.

Submit a check-in memo by Friday at noon (under the check in memos tab on Blackboard) by Friday at noon that describes your progress on these problems (and some other things). There are specific questions to answer there. This goes privately to Dr. B who will then give you feedback.

Content Objectives - Module 3

By doing this homework you will demonstrate that you are able to

1. Use “big-O” order notation to describe an asymptotic upper bound for various functions.

2. Compute basic probabilities.

3. Make connections between complexity, probability, and security.

Proficiency Problems

1. (Obj. 1) Find an asymptotic upper bound for each of the following functions in n. Which of them are polynomial and which are negligible?

(a) f1 = 2n 3 − 3n2 + n

(b) f2 = 3 · 2n − 2n + 1 (c) f3 =

√ 2n + 1

(d) f4 = 2n

2n/2

(e) f5 = 3 5n2 −n

2n2 + 3n + 1

(f) f6 = 2 1 3 n+3

(g) f7 = log2(n) 2n

2. (Obj. 1) Suppose the number of operations of the most efficient attack against a cipher is

f(n) = e2n 1/3 ,

where n is the key length. Why is f(n) sub-exponential, but not polynomial, in n? Compute the effective key length log2(f(n)) for n = 128, n = 1024, and n = 2048.

3. (Obj. 2) Let Ω = {0, 1}8 be a probability space with a uniform probability distribution. Compute the probability that a randomly chosen byte (i.e., string of 8 bits) contains an equal number of zeros and ones.

4. (Obj. 2) Two perfect dice are rolled and the random variables which give the numbers on the dice are called X and Y . Compute

Pr[X + Y ≥ 0] and Pr[X + Y ≥ 0 | X −Y = 0].

Are the random variables X + Y and X − Y independent? Determine the expected value, variance, and standard deviation of both X + Y and X −Y .

5. (Obj. 2) Suppose that 100 bits are generated uniformly at random and that additional bits are produced by XORing the preceding 100 bits. Are the new bits uniformly distributed? Does this construction give a random bit generator?

6. (Obj. 3) Provide reasons for Kerkhoff’s principle and discuss possible counter-arguments.

7. (Obj. 3) Show that the one-time pad is not perfectly secret if a key is used twice.

8. (Obj. 3) Let M be the plaintext space and K the key space of a perfectly secure encryption scheme. Show that |K| ≥ |M|. (Hint: Suppose ek(m0) = c. How many different plaintext-key pairs give the ciphertext c?)

Challenge Problems

Justify your answers with complete sentences explaining your reasoning.

9. Let Pr be a uniform distribution on the sample space Ω with |Ω| = n. If k ≤ n samples are indepen- dently chosen, then the probability p that all k values are different is

p = k−1∏ i=1

( 1 −

i

n

) (a) Show that the probability 1 −p that some value being repeated satisfies

1 −p ≥ 1 −e− k(k−1)

2n .

(b) Determine the smallest number k such that p is approximately 1/2.

10. Prove that the function L(x) = e

√ (lnx)(ln lnx)

is subexponential. That is, prove the following two statements:

(a) For every positive constant α, no matter how large, L(X) = Ω((ln X)α).

(b) For every positive constant β, no matter how small, L(X) = O(Xβ).