A printable PDF is available.

# Homework 9 – Due Tuesday, April 4

- Consider a cryptographic hash function
*f:{0,1}*that satisfies the preimage resistance property and second preimage resistance property, even though it only works on fixed-size input blocks. Joe needs a function like this, but it has to work on^{n}-> {0,1}^{h}*pairs*of*n*-bit inputs, so he defines*g:{0,1}*as^{n}×{0,1}^{n}-> {0,1}^{h}

Is this function preimage resistant? Does it satisfy the second preimage resistance property? Justify both answers!*g(x,y) = f(x XOR y) .* - Prove that a hash function that satisfies the collision resistance
property also satisfies the second preimage resistance
property. (
*Hint: Write the statement you're trying to prove as an implication, and then prove the logical contrapositive.*) - Does a hash function that has second preimage resistance also
satisfy the preimage resistance property?
To answer this question, consider a hash function
*H(x)*that produces*k*-bit hash codes, and satisfies all three of the hash function security properties. Now construct a hash function*H'(x)*that produces*(k+1)*-bit hash codes as follows: If*x*is exactly*k*bits long, then output*0||x*(a single 0 bit followed by*x*); otherwise output*1||H(x)*(a single 1 bit followed by the*H*-hash code of*x*). Is*H'(x)*second preimage resistant? Is it preimage resistant? Justify your answers!