Elliptic curve one time signatures

Question

This is kind of an academic question, but I wonder if it's possible to build an intentionally one-time signature scheme with elliptic curves?

I assume you could do it by supplying ECDSA with deterministic input instead of randomness during signing, resulting in "sudden death" if two messages are signed by the same key. This however includes all the complexity of ECDSA. I feel like there's probably a way to get one time signatures out of elliptic curves via some simpler construct.

(One-time-ness is normally an undesirable property, but imagine it's a desired property. You explicitly don't want multiple signatures per secret key, so you want to strongly discourage that by making it result in loss of security.)

Answer 1

Supplying ECDSA with deterministic input doesn't make for a one-time signature—RFC 6979 chooses the per-signature secret as a deterministic but secret function of the message. However, there is a variant of ECDSA—or EdDSA—that could probably work.

• In ECDSA, a public key is a point $A$ on a curve with standard base point $G$, and a signature on a message $m$ is a pair of integers $(r, s)$ such that $$r = f\bigl(x([H(m) s^{-1}] G + [r s^{-1}] A)\bigr),$$ where $f$ maps a coordinate to a scalar. For any particular $r$, there are only approximately two $s$ values that work—$s \equiv \pm [H(m) k^{-1} + r k^{-1} a] \pmod n$, where $k$ is the per-signature secret, $a$ is the secret scalar such that $A = [a]G$, and $n$ is the order of the group. (There may be a few other $s$ values because of the weird $f$, but there aren't many.)

  Instead of choosing $r$ at signing time, you could choose $r$ at key generation time: then a public key is a pair $(A, r)$ and a signature is an integer $s$ satisfying the same equation. Then publishing two different signatures, that is two different $s$ values for a single $r$ value and therefore for a single per-signature secret $k$, would leak the private key to anyone who can solve a trivial linear equation.

• Similarly, in EdDSA, a signature is a pair $(R, s)$ of a point $R$ on the curve and an integer $s$ such that $$[8 s]G = [8]R + [8 H(R, A, m)] A.$$ Again, you could make $R$ part of the public key $(A, R)$, leaving only $s$ in the signature.

This doesn't really enable any simplifications—where previously you could have (say) 32-byte public keys and 64-byte signatures, now you have 64-byte public-keys and 32-byte signatures, and the cost of signing and verifying is exactly the same. But it does guarantee one-time signatures on threat of leaking the private key.