Assignment 2: Due Wednesday, February 13

1. Textbook, page 38, Exercise 2.6(b)

2. Consider the following encryption scheme: The keyspace 𝒦 is the set of all permutations of 0, 1, ..., 7 and both the plaintext message space ℳ and the ciphertext message space 𝒞 are the set of all 8-bit bytes. The encryption scheme Π = (Gen, Enc, Dec)
   • Gen: Selects a random permutation from 𝒦
   • Enc: To compute Enc_k(m), permute the bits of m using permutation k. For example, if k is a permutation that maps 0 to 7, 1 to 6, 2 to 5, 3 to 4, and so on, it will reverse the bits, so the encryption of plaintext byte “11001010” would produce ciphertext “01010011.”
   • Dec: To compute Dec_k(c), the inverse of permutation k is applied to c.

   Prove that Π is not perfectly indistinguishable. You must define a specific adversary 𝒜 and use Definition 2.5 directly (you cannot use any of the equivalent formulations).

3. You solved Exercise 2.6(a) in Assignment 1, so think about that situation a little more. In that problem, plaintext and keyspace sets had sizes |ℳ| = 5 and |𝒦| = 6. Theorem 2.10 established the |𝒦| ≥ |ℳ| is a necessary condition for a perfectly secret encryption scheme, and that condition is satisfied in this case. Is that condition sufficient? In other words, is it possible to have a perfectly secret encryption scheme where |ℳ| = 5 and the Gen draws a key uniformly from a keyspace with |𝒦| = 6? (Hint: Make sure you completely understand the proof of Theorem 2.10! Also note that this is not asking about the specific encryption scheme from Exercise 2.6(a) – I’m asking if there is any way to define a perfectly secure scheme for the given plaintext and keyspace sets.)

4. Textbook, page 40, Exercise 2.13(a)

5. At the beginning of Chapter 3, the authors have a discussion about key sizes that would be sufficient for concrete security against brute force attacks (we also did this in class, using supercomputer speeds from the Top 500 list). For this problem, you should do a similar analysis but using extreme, over-the-top assumptions about the attacker’s computational capabilities (obviously far, far beyond what any conventional computer, now or ever, could do).

   Consider if you could convert the entire planet into one big computer (suggestion: read The Hitchhiker’s Guide to the Galaxy if you haven’t) — do some research and find a good estimate for how many atoms are in the Earth, making sure you use a reliable source and include a citation in your answer. Assume that you can make a logic gate using just 8 atoms. Next, assume that you can clock those gates at the fastest imaginable speed, the frequency of ultraviolet light, which would be a 1,000 THz computer, and testing a key takes 1000 Boolean operations. Finally, a “super-secure” cipher is one that cannot be brute-forced (on average) in under 128 years. What keysize would need to be used so that a cipher is “super-secure” against attacks using this ultra-fast full-planet computer? You can (and should!) estimate all values as powers of two when you solve this problem, and be sure to show your work.

6. Textbook, page 102, Exercise 3.1

7. Textbook, page 102, Exercise 3.4