13
$\begingroup$

ECDSA signatures depend on parameter k that is chosen by the signer. As a result, there are many signatures for the same private key d and message m.

What I want to achieve is a deterministic signature. That is, given private key d and message m, there should be only one valid signature. I could go with RSA (with deterministic PKCS#1 v1.5 padding) but would prefer ECDSA if possible as it is almost as widely deployed and has smaller key and signature sizes.

RFC 6979 describes how k can be generated deterministically but it doesn't solve my problem because those who verify the signature can't verify that the signer did actually follow RFC 6979 (I'm not aware of any such method).

I'm thinking about imposing some additional requirements on signers that others can easily verify.

For example, what if I require that all signers derive k using a formula like this:

k = H(m) * d

where d is private key, and H is hash function. Then in signature (r, s), r is x-coordinate of

k x G = H(m) * d x G = H(m) * Q

where G is generator, Q = d x G is public key, and x denotes EC multiplication.

Unless I'm getting EC math wrong, this choice of k derivation function has the advantage that it can be easily verified by multiplying public key point by H(m) and comparing the x-coordinate of this point with r from the signature. At the same time, it seems, all the security requirements for k are still satisfied: it is private since it is derived from private key and it is different for each message as it depends on message hash.

Will it work? Any other ways to create deterministic signatures?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You already mentioned another way "to create deterministic signatures". $\:$ BLS is another way to create signatures where there is at most one valid signature per message. $\;\;\;\;$ $\endgroup$
    – user991
    Jul 17, 2015 at 0:41
  • $\begingroup$ Also Eddsa is deterministic tools.ietf.org/html/draft-irtf-cfrg-eddsa-05 $\endgroup$
    – Nikkolasg
    Oct 10, 2016 at 19:03

2 Answers 2

Reset to default
9
$\begingroup$

DSA relies on $k$ being independent from $d$. You define $k$ as:

$k=z^\prime d\mod n$

Substituting $k$ in the signing equation you get:

$s = k^{-1} (z+rd) \mod n$

$s z^\prime d = z + rd \mod n$

$d=z (sz^\prime -r)^{-1} \mod n$

The attacker knows everything on the right side and can recover the private key.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ah broken, thanks! Any suggestions how to make ECDSA deterministic if it is possible at all? $\endgroup$
    – Tony
    Jul 17, 2015 at 20:57
  • $\begingroup$ @DrLecter The OP wants verifiably deterministic signatures and already linked that RFC. $\endgroup$
    – CodesInChaos
    Jul 18, 2015 at 7:12
  • $\begingroup$ Ah, didn't see that. $\endgroup$
    – DrLecter
    Jul 18, 2015 at 7:13
  • $\begingroup$ @CodesinChaos I think you wanted to write $z'$ instead of $z$ (since the signing equation is $s=k^{-1}(H(m)+rd)$ and $H(m)=z'$). $\endgroup$
    – 111
    Jul 19, 2015 at 17:43
0
$\begingroup$

Koblitz and Menezes gave deterministic versions of ECDSA and ECSchnorr here: https://eprint.iacr.org/2015/140

The deterministic version is proven to be as secure as their probabilistic counterpart, but as mentioned by the authors, their 'proof' is an unnatural one though without using random oracle model.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Isn‘t that variant also using the private key as a hash input? This would make it non-verifiably deterministic only. $\endgroup$
    – lxgr
    Jul 15, 2021 at 11:58

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.