2
$\begingroup$

With ECDSA (and possibly DSA too) I'm aware that if the same value for $k$ is used with the same private key $D_A$ to sign two different messages, then anyone possessing the two messages $m_0$ and $m_1$ and two signatures $(r_0, s_0)$ and $(r_1, s_1)$may recover $D_A$ trivially (as in fail0verflow's PS3 private key recovery).

Does there exist a way of using this weakness to make a signature system where each private key can only be used once, with the deterrent that if the private key is used a second time, everyone can calculate and use it?

This would require an extra verification step to prove that $k$ was deterministically generated from $D_A$ (in a prescribed manner) so that signings would only be valid, if they used the single, known way of calculating $k$ (without revealing $k$). Otherwise, if a malicious signer were to use different $k$s for the same $D_A$ there would be nothing to deter it, so $k$ must be a deterministically generated from $D_A$.

(This is different from RFC 6979 which uses a hash of the message and $D_A$ to ensure a good pseudo-random value for $k$.)

From answers to With ECDSA is there a way for the verifier to calculate any properties of $k$? and With EC secp256k1 is there a way of transforming a function of the private key to a function of the public key? it looks like this is impossible.

Is there a way of making a single-use signature scheme, where a second use of a private key discloses that private key to the world?

$\endgroup$
  • $\begingroup$ I wonder if it would be possible to make $k$ a constant multiple of $D_A$. That way the verifier could check that $r$ matches the public key. Not immediately seeing if this will allow finding the private key from just one signature. $\endgroup$ – otus Nov 6 '15 at 10:40
2
$\begingroup$

Trivial solution: generate a random $k$ as part of the private key and include $r$ as part of the public key.

The verifier uses $r$ from public key, so the signer must use the same $k$ for every valid signature. The signer could create multiple related public keys and reuse $D_A$, but then, they might as well just create multiple key-pairs in the first place.

$\endgroup$
  • $\begingroup$ Just spent 5 minutes trying to understand what you'd written, then a light bulb came on. Thanks, that's so straightforward. $\endgroup$ – Thomas Von Panom Nov 6 '15 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.