Question 2 (5 marks): (Digital Signatures) Suppose that h is a hash function taking long messages as input and producing 256 bit outputs and that M is a long message. Consider the following idea for constructing a signature scheme: - A private signature key Ks is a pair of randomly generated sequences x1,,x256 and y1,,y256, both of length 256 , where each value xi and yi is a 256 bit message. - The corresponding public verification key Kv is the pair of sequences h(x1),,h(x256) and h(y1),,h(y256) - To sign message M, where the hash h(M) is the sequence of bits b1b256, define sign(M,Ks)=(M,z1z256) where zi=xi if bi=0 and zi=yi if bi=1. 1. Explain how you could verify this signature is correct: what does the verification function V(Kv,(M,r1r256)) do to check that (M,r1r256) is message M signed using the signature key corresponding to Kv ? 2. Explain why this scheme is secure - why is it hard for an attacker to forge a signed document that passes the test? Clarify what assumptions on the hash function are needed for your argument. 3. Is it safe to use the same private key to sign more than one message? If not, explain what an attacker could do to attack a user who does this