# Elliptic curve one time signatures

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.)

• 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 = 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.
• Neat. Could r be chosen deterministically based on a hash of A so you don't have to explicitly specify it, making public keys smaller? Nov 5, 2019 at 13:57
• @AdamIerymenko No, because the signer needs to know the secret $k$ such that $R = [k]G$ in order to make the signature. (For ECDSA, $r = x(R)$.) Nov 5, 2019 at 15:59