Birthday Attack. Let H be an ideal hash function that produces an n-bit output. By ideal, we mean that as far as we can tell, each hash value is independent and uniformly distributed in {0,1}n. Trivially, we can go through 2n + 1 different values and we are guaranteed to find a collision. If we're constrained for space, we can just store 1 input-output pair and keep trying new inputs until we hit the same output again. This has time complexity O(2n), but has O(1) space complexity. Alternatively, we could compute the hashes of about O(2n/2) different inputs and store all the input-output pairs. As we saw in the text, theres a good chance that some two of those outputs would collide (the birthday paradox). This shows that we can achieve a time-space trade-off: O(2n/2) time and O(2n/2) space.

1. (Easy) Show that the time-space trade-off is parameterizable: we can achieve any space complexity between O(1) and O(2n/2) with a corresponding decrease in time complexity.
2. (Very hard) Is there an attack for which the product of time and space complexity is o(2n)? [Recall the little oh notation.]
3. Hash function properties (again). Let H be a hash function that is both hiding and puzzle-friendly. Consider G(z) = H(z) zlast where zlast represents the last bit of z. Show that G is puzzle-friendly but not hiding.
4. Randomness. In ScroogeCoin, suppose Mallory tries generating (sk, pk) pairs until her secret key matches someone elses. What will she be able to do? How long will it take before she succeeds, on average? What if Alices random number generator has a bug and her key generation procedure produces only 1,000 distinct pairs?