Sections 8.1-8.2, due Wednesday November 3

1. (Difficult) The proof of the proposition on page 221 is a little fuzzy to me. I follow most of it, but another explanation in class would be helpful. Can a hash function be anything that satisfies those three conditions on pages 218-219? Was the simple example in 8.2 really a hash function because it was not strongly collision-free?

2. (Reflective) The simple hash example seemed very easy to compute, but did not seem like it would be very useful. XORing the columns would get rid of all the information in the message. Would you just use this type of has function if you were given (m, h(m)) and were checking to see if the message m, actually matched h(m)? The only other time I have heard of something similar to hash functions is when we were asked to read about one-way functions. One-way functions are turning out to be very useful functions to use in cryptography.