Verifiably deterministic ECDSA signatures?

Question

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?

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. $;;;;$ — , Jul 17 '15 at 00:41
Also Eddsa is deterministic https://tools.ietf.org/html/draft-irtf-cfrg-eddsa-05 — Nikkolasg, Oct 10 '16 at 19:03

CodesInChaos · Accepted Answer · 2015-07-17T10:45:58.927

9

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.

edited Jul 17 '15 at 10:45

answered Jul 17 '15 at 09:20

CodesInChaos

24,841
2
89
128

Ah broken, thanks! Any suggestions how to make ECDSA deterministic if it is possible at all? – Tony Jul 17 '15 at 20:57
@DrLecter The OP wants verifiably deterministic signatures and already linked that RFC. – CodesInChaos Jul 18 '15 at 07:12
Ah, didn't see that. – DrLecter Jul 18 '15 at 07:13
@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'$). – 111 Jul 19 '15 at 17:43

score 0 · Answer 2 · answered Mar 13 '17 at 07:17

0

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.

answered Mar 13 '17 at 07:17

Tan

91
1
5

Isn‘t that variant also using the private key as a hash input? This would make it non-verifiably deterministic only. – lxgr Jul 15 '21 at 11:58

Verifiably deterministic ECDSA signatures?

2 Answers2