Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
-
$\begingroup$ Your answer is better than mine was. $\endgroup$– fgrieu ♦Commented Jun 3, 2019 at 21:10
-
$\begingroup$ Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$? $\endgroup$– MyriaCommented Jun 3, 2019 at 21:26
-
$\begingroup$ That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer. $\endgroup$– ckamathCommented Jun 3, 2019 at 21:28
-
4$\begingroup$ @grawity EdDSA has essentially no relation to ECDSA except that they are both signature schemes using elliptic curves. EdDSA is based on Schnorr signatures, which are cheaper to compute and admit security theorems; ECDSA was carefully designed to make every design decision the stupid way in order to avoid Schnorr's patent in the early '90s, and consequently is costlier to compute and harder to analyze the security of. More details: blog.cr.yp.to/20140323-ecdsa.html $\endgroup$ Commented Jun 4, 2019 at 15:33
-
2$\begingroup$ A forgery attack on Schnorr's system, where a signature under public key $A$ on message $m$ is $(h, s)$ such that $H(B^s A^h, m) = -h$, and a forgery attack on EdDSA, where a signature under public key $A$ on message $m$ is $(R, s)$ such that $B^s = R A^{H(R, m)}$, are trivially interchangeable: write $h = H(R, m)$ or $R = B^s A^h$ to interchange them. So Schnorr security implies EdDSA security and vice versa. (Here I wrote everything in multiplicative notation; EdDSA is obviously done over curves which are usually written additively, but the point remains unchanged.) $\endgroup$ Commented Jun 4, 2019 at 15:41