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?
$\begingroup$
$\endgroup$
7
-
3$\begingroup$ Are you looking to get a deterministic signature? If so, see datatracker.ietf.org/doc/html/rfc6979 $\endgroup$– knacccCommented Aug 11, 2023 at 3:02
-
$\begingroup$ @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. $\endgroup$– MelabCommented Aug 12, 2023 at 16:56
-
3$\begingroup$ 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? $\endgroup$– knacccCommented Aug 12, 2023 at 19:26
-
$\begingroup$ @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.) $\endgroup$– MelabCommented Aug 12, 2023 at 23:34
-
$\begingroup$ 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 $\endgroup$– fgrieu ♦Commented Aug 13, 2023 at 16:39
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ What is the key-size-to-strength ratio? $\endgroup$– MelabCommented Aug 19, 2023 at 20:35
-
$\begingroup$ 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. $\endgroup$ Commented Aug 20, 2023 at 8:02