5
$\begingroup$

By design, EdDSA requires a $b$-bit string as the secret key $k$, and when signing, it is expanded to a $2b$-bit string $H(k)$, some bit-twiddling is done, and the first half is used as the private key in the signature. [1]

The curve will have a $b$-bit security level, and solving discrete log can be done in $b \over 2$.

Why is it that EdDSA requires a $b$-bit secret key instead of only $b \over 2$-bit which seems like it would provide the same level of security as the curve itself?

$\endgroup$
7
$\begingroup$

One possible reason (and probably the one that was behind that design choice) is to avoid multi-target attacks.

Consider a setup where there are $k$ public/private key pairs, and the attacker's goal is to find one of these private keys. The attacker does not care which private key is obtained; getting any of them is a "win". For instance, the attacker wants to make a fake X.509 certificate by recovering the private key of a certificate authority: any private key in a chain to any root CA in the set of trusted root CA will do. A brute force attack on the $b$-bit seed will succeed with average cost $2^b/k$ (the attacker computes the public key for each potential $b$-bit seed, then looks up the public key in the set of targets; the looking-up does not involve complicated maths and can be done in "negligible" time, compared to the computation of the public key). If $b = 128$ and $k$ is large, then this can be substantially less than $2^{128}$.

From an "academic" point of view, this means that 128-bit seeds only provide "64-bit security": if there is a set of $2^{64}$ targets, then the attack succeeds in cost $2^{64}$, while the defenders collectively spent an effort of only $2^{64}$. Bumping seed size up to 256 bits is an easy and inexpensive way to prevent that kind of academic break.

| improve this answer | |
$\endgroup$
  • $\begingroup$ One may also want to note that multi-target attacks against multiple discrete log instances scale sublinearly. $\endgroup$ – SEJPM Jan 30 at 19:49
  • $\begingroup$ I've restructed the text a bit for better readability; roll back if you disagree. I've left the quotation marks even though I don't agree with most of them (in case you want to review your own answer). This comment will self destruct... $\endgroup$ – Maarten Bodewes Jan 30 at 20:11
3
$\begingroup$

The reason the private key is approximately the same order as the curve is due to the number of possible public keys being equal to the order of the cyclic subgroup generated by G.

This varies from curve to curve, but ultimately a shorter private key would end up excluding some possible elements of the subgroup, weakening the crypto.

The fact than the DLP can be solved in 2^n/2 is irrelevant here, as that attack doesn’t brute force the keyspace. It uses Pollard Rho.

Whilst it’s true some curves generate a relatively smaller keyspace than 2^n such as curve25519, whose co-factor effectively results in a keyspace of (2^n)/8 we still use 32-byte keys for simplicity and cross compatibility. Libraries will clamp keys as necessary.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "a shorter private key would end up excluding some possible elements of the subgroup, weakening the crypto"; is this last part true? If you have a random oracle $f$ that maps a $\ell \ge n/2$ bit value into an $n$ bit multiplier, can you use that fact to solve the DLog problem for the point $f(r)G$ (random $r < 2^\ell$) in less than $O(2^{n/2})$ time (the time you'd get for a random point)? I cannot think of a method... $\endgroup$ – poncho Jan 30 at 19:23
  • $\begingroup$ Could still be the reason even though it cannot be proven to be a valid reason, of course. Almost anything can be a reason to do stuff. $\endgroup$ – Maarten Bodewes Jan 30 at 20:12

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.