The Schnorr Signature schemes works as follows Choose a prim

The Schnorr Signature schemes works as follows: Choose a prime number q and a generator of g Z_q of prime order q. Choose a Hash function H:{0, l}* rightarrow Z_q; H, q and g are publicly known. Let M={0, 1}* be the set of binary strings that need to be signed. To sign a message M, Alice chooses a private key x Z_q\\{0} (that is x Z_q but x notequalto 0) and a randomly chosen (say a per-message signing key) x Z_q\\{0}. 1. Compute r = g^k mod q. 2. Compute e = H(M||r) 3. Compute s =(k-xe) The message, signature pair consists of (M, (s, e)). Note that s, e Zq So the public parts are g, q, y, s, e and r. Private parts are k and x. To verily the signature on M, Bob computes the following: Compute r_v = g^sy^e Compute e_v =H(M|| r_v) If the computed value e_v = e, then the signature is valid. If the message size |M| = (q-l)/2, then given one hash r, what is the probability of finding another value r\' such that H(M||r)=H(m||r\') for a given message M?

Solution

If the Schnorr identification protocol is secure, then the Schnorr signature scheme is secure in the random oracle model. Specifically, suppose there is an efficient adversary A that produces a valid signature forgery with probability while making at most qH hash function queries and qS signature queries. Then there is an algorithm B that successfully impersonates the prover in the Schnorr identification protocol with probability at least /(qH + 1) (qH + qS + 1)/r. Proof sketch. Suppose we are given an public key P, Q = [a]P for the Schnorr identification scheme and an adversary A that breaks the signature scheme. We construct an adversary B that uses A to attack the ID scheme. Adversary B will act as a challenger in the signature game, responding to A’s signature and hash function queries. B will then use the information it receives from A to interact with the verifier V in the ID protocol. Before describing B we make a simplifying assumption. By modifying A to make one more hash function query if necessary, we assume that if A’s forgery is (m , R , s ) then mkR was queried to the hash function at some point. (This is where the qH + 1 comes from in the probability statement.) We now describe B. First suppose that A makes only the hash query mkR and no signature queries. When A makes this query, B will use R as the first message in the ID protocol. B then obtains a challenge e from the verifier V and returns this value for H(m , R ). The s component of the adversary’s forgery is then sent as the final message in the ID protocol. If the forgery is valid, then we have [s ]P = R + [e ]Q, and therefore the verifier accepts and we have broken the ID scheme. Now we allow A to make signature queries on messages mi . We simulate a signature in the same way we simulated transcripts for the ID scheme above: we choose random ei and si and set 3 Ri = [si ]P [ei ]Q. We then set the value of the hash function on input mikRi to be H(mikRi) = ei . Since si and ei are random, this value looks random to the adversary, as required. Now we allow A to make more hash queries ˜mjkR˜ j . For now assume that mkR is the first hash query. For other hash queries, we either use the preprogrammed value (for example, if m˜ jkR˜ j = mikRi for the ith signature query), or we choose a new random value ˜ej . From the point of view of the adversary, these responses are consistent with H being a random function. Finally, since the hash query used by A in his forgery may not be the first one, we use a “guessing” argument: namely, we pick in advance a random [1, qH + 1] and hope that A will forge on the th hash query. Since our chances of being correct are 1/(qH + 1), our success probability is reduced by this factor. In detail, adversary B is given a public key (P, Q) for the Schnorr identification protocol and works as follows: • Initialization: 1. Choose a random R [1, qH + 1]. 2. Send pk to A as the signature public key. • On receiving the ith signature query mi , do the following: 1. Choose random ei , si R [1, r]. 2. Set Ri = [si ]P [ei ]Q. 3. Return i = (Ri , si). 4. Store ei as the value of H(mikRi). • On receiving the jth hash query ˜mjkR˜ j , do the following: 1. If the value of H( ˜mjkR˜ j ) has already been set (during a signature query or a previous hash query), return that value. 2. If j 6= , choose a random ˜ej R [1, r], and set H( ˜mjkR˜ j ) = ˜ej . 3. If j = : (a) Send R˜ j to V as the first step in the ID protocol. (b) Obtain a challenge e from V. (c) set H( ˜mjkR˜ j ) = e . • On receiving a forgery attempt (m , R , s ) from A, send s to V as the final step in the ID protocol. If the jth hash query is mkR (which happens with probability 1/(qH + 1) and the adversary’s forgery is valid (which happens with probability ), then we have [s ]P = R + [H(m kR )]Q = R + [e ]Q and therefore V accepts. The term (qH + qS + 1)/r in the probability statement comes from the chance that there will be a collision among the points Ri chosen in response to signing queries; we omit the details. Corollary 3. If the discrete logarithm assumption holds in E(Fq), then the Schnorr signature scheme is secure.