3
$\begingroup$

When a Schnorr signature is created, the number $r$ is concatenated with the message to produce a new value which is then hashed to give a number represented by $e$. The number $e$, accompanied by some other data that is used during validation, will then be sent over to a signature verifier. The signature verifier will then try to recompute the number $r$ using the information given to them and once they have done that, they will concatenate the number $r$ that they computed with the received message and use the same hash function to get an output represented as $e\prime$. If $e\prime = e$, the signature is valid.

My question is: does the hash function that is used contribute to the overall security of the signature algorithm or is just used when signing to compress the concatenation of the number $r$ and the message into a fixed number of bits?

$\endgroup$
5
$\begingroup$

It does contribute to the security. In particular, the hash function $H$ must be “random prefix preimage resistant” in order to be safe from Key Only forgeries and “random prefix second preimage resistant” in order to be safe from Known Message forgeries.

By “random prefix preimage resistant”, we mean that given an output value $e$ and a random $r$, it is hard to find an $m$ such that $H(r||m)=e$ (and in the second preimage case, even if provided with an example $m$, it is hard to find a second example).

If it were easy, then we could choose an arbitrary $e$ and $s$ and (following the Schnorr validation process) compute $r=g^sy^e$ and then solve our preimage problem for $e$ and $r$ to get a message $m$ for which $(s,e)$ is a valid signature. Note that we do not necessarily have control over $m$ and so this attack is a Key Only Attack to create an Existential Forgery and the scheme would not be EUF-KOA secure.

Similarly, in the second preimage case we could take an existing signature for a message $m$ and create a second message $m’$ with $H(r||m)=H(r||m’)$. The signature $(s,e)$ for $m$ would also work as a signature for $m’$ and the scheme would not be EUF-KMA secure.

$\endgroup$
6
  • $\begingroup$ Those are necessary properties. They're not known to be sufficient. $\endgroup$
    – Maeher
    Dec 7 '21 at 8:19
  • 1
    $\begingroup$ Agreed, but a necessary property is all that is required to show that the hash function does contribute to the security. FWIW Neven, Smart an Warinschi showed sufficiency in the generic group model. $\endgroup$
    – Daniel S
    Dec 7 '21 at 8:26
  • 2
    $\begingroup$ Yes, it answers the question. I merely thought the answer might be misunderstood. $\endgroup$
    – Maeher
    Dec 7 '21 at 9:32
  • 1
    $\begingroup$ @kelalaka: No, in general the property that a group is generic/black box tends/has to be an assumption (for example, this assumption is widely-made about elliptic curve groups). Generic groups are in the same camp as PRPs and PRFs: theoretical constructs from which we hope our primitives are indistinguishable. from $\endgroup$
    – Daniel S
    Dec 7 '21 at 10:11
  • 1
    $\begingroup$ So, as I know. Therefore showing in the generic model is a theoretical work to show us that as long as there is no special property of the group we expect to be safe. $\endgroup$
    – kelalaka
    Dec 7 '21 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.