1
$\begingroup$

Assume a 256-bit ECDSA private key used with Secp256k1 and SHA-256. This key signs multiple different messages in a fully deterministic manner as described in RFC-6979, so signing the same message always produces the same signature.

A quantum attacker obtains the first 32 bytes of each signature. However, the rest of each signature, the messages, the private key and the public key remain concealed from them.

Can the attacker prove that the signatures were produced with the same private key?

(This is a modification of my previous question: "Given multiple ECDSA signatures with the same key, what can a quantum attacker learn?")

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Can the attacker prove that the signatures were produced with the same private key?

The first 32 bytes are the $r$ value; that's the x-coordinate of the value $kG$, where $k$ is a random value, selected independently of the key.

Because the keys in a partial signature are independent of the key, they don't leak any information about the key. This includes whether two different partial signatures were generated with the same key.

Improve this answer
$\endgroup$
8
  • $\begingroup$ However, if it's a fully deterministic ECDSA, it allows us to infer which message(s) (whose contents're unknown) were being signed. $\endgroup$
    – DannyNiu
    Feb 13 at 4:30
  • $\begingroup$ @DannyNiu: actually, unless they also had the private key, no, it wouldn't - deterministic ECDSA stirs in the private key with the message to generate $k$ (otherwise, just knowing the message would allow anyone to recompute $k$, which would be bad) $\endgroup$
    – poncho
    Feb 13 at 4:32
  • $\begingroup$ But that allows observing $R=kG$, since in RFC-6979, only message hash and the private key are mixed in (and private key is static). Unless they've implemented the newer IETF draft, where there's additional randomness $\endgroup$
    – DannyNiu
    Feb 13 at 5:02
  • $\begingroup$ @DannyNiu , Poncho, I apologize, I forgot to mention we are talking about fully deterministic ECDSA. I will update the question to reflect that. $\endgroup$
    – ostrich
    Feb 13 at 5:42
  • $\begingroup$ @DannyNiu: since a quantum attacker was posited, they could already observe $k$ directly. In any case, I'm not sure what you mean; just because the attacker knows that there's a mapping from message to $k$ doesn't mean he knows what that is (and since he doesn't know the private key, he doesn't). And, this mapping is believed to be quantum-safe, and so a Quantum Computer doesn't help him there. $\endgroup$
    – poncho
    Feb 13 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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