Score:3

Is the security of a Schnorr signature dependent on the hash function that is used?

de flag
CCS

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?

Score:5
ru flag

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.

cn flag
Those are *necessary* properties. They're not known to be sufficient.
Daniel S avatar
ru flag
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](http://www.neven.org/papers/schnorr.html) showed sufficiency in the generic group model.
cn flag
Yes, it answers the question. I merely thought the answer might be misunderstood.
kelalaka avatar
in flag
Is there a way to show that a group is generic?
Daniel S avatar
ru flag
@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
kelalaka avatar
in flag
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.
real-or-random avatar
th flag
@Maeher The theorem by NSW'09 should be taken with at least a grain of salt. Brown'15 (https://eprint.iacr.org/2015/509.pdf) claims to have a counter-example. (I admit I have neither read NSW'09 nor Brown'15 in enough detail to have an solid opinion here.)
cn flag
@real-or-random you may have wanted to tag Daniel S instead.
real-or-random avatar
th flag
Daniel S is notified automatically as the author of the answer. But yeah, don't ask me why I tagged you, sorry for the unnecessary notification...
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.