Score:0

Crypto

Elliptic curve signature scheme without a nonce

Melab

8/11/24, 1:55 AM

ECDSA and EdDSA both require the generation of a single-use value. Are there any elliptic curve signature schemes in existence which don't require nonce and maintain the usual security strength equal to that offered by the curve?

1 + 7

elliptic-curves

knaccc

8/11/24, 3:02 AM

Are you looking to get a deterministic signature? If so, see https://datatracker.ietf.org/doc/html/rfc6979

Melab

8/12/24, 4:56 PM

@knaccc No. RFC 6979 involves signature schemes which use nonces, even if it makes them deterministic. I am looking for a signature scheme that doesn't require an additional value like DSA and ECDSA do.

knaccc

8/12/24, 7:26 PM

As soon as the nonce is deterministic, it's no longer technically a nonce, since the value will be used more than once if the same message is signed in the future. It can just be thought of as part of the signature calculation. Can you explain your motivation to avoid a nonce?

Melab

8/12/24, 11:34 PM

@knaccc An elliptic curve signature scheme that doesn't necessitate a non-reusable value which, if reused with a different combination of values, would break the scheme. RSA as a signature scheme is an example of what I mean. (Good grief.)

fgrieu

8/13/24, 4:39 PM

There is a difference in nature between DSA or ECDSA on one hand, and EdDSA on the other hand. For the former kind we need a TNRG to generate a nonce. For the later we don't, and the closest thing to a nonce will be reused, and safely so, anytime it's twice computed the signature of the same message. Thus the risk of catastrophic private key leak by nonce reuse thru broken TRNG exists in the former kind, not the later. I get why due to this, we would not want DSA or ECDSA as standardized (with random nonce). It's less clear for EdDSA (or DSA/ECDSA modified to be deterministic). @Melab

Maarten Bodewes

8/13/24, 7:50 PM

I'm not sure this can be answered in any meaningful way if it is not explained *why* the internally generated nonce needs to be avoided. Are you afraid of leaks? Side channels? State size / memory usage? As for RSA, maybe we can see the result of the MGF1 function as a "data dependent nonce". It's at this point just a label.

Melab

8/17/24, 3:41 PM

@fgrieu EdDSA includes a deterministically-generated nonce, but this would arguably be stripped away if someone wanted the core algorithm. I'm only interested in the "cores" of these algorithms and those of (EC)DSA and EdDSA are similar in this respect.

Score:3

Crypto

Mehdi Tibouchi

8/16/24, 7:42 AM

I suppose one meaningful way to interpret the question is to phrase it as follows: “does there exist an elliptic curve-based unique signature scheme?” (i.e., in which there is only one valid signature on each message, as is the case for RSA-FDH).

In that case, BLS signatures fit the bill, although of course, it's really pairing-based rather than EC-based, so you can only instantiate it over pairing-friendly curves, and verification is substantially more expensive than in Schnorr-like constructions.

+ 2

Melab

8/19/24, 8:35 PM

What is the key-size-to-strength ratio?

Mehdi Tibouchi

8/20/24, 8:02 AM

This is not well-defined (in the same way as you cannot give a key-size to strength ratio for RSA, because the best known attack is subexponential; parameter selection is also complicated by the fact that one needs to select the embedding degree). But for typical security levels, keys are not much larger than for usual ECC. I think the standard choice nowadays at the 128-bit security level is a curve over a 381 bit field.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Elliptic curve signature scheme without a nonce

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.