[CFRG] Why we use ECDH instead of traditional DH

[Daniel Brown <[e-mail]>]

Hi D. J. Bernstein,

Beyond historical interest, is the main point here ("why ECDH, not FFDH")
to help work out clearer criteria for future CFRG decisions?

On the historical side, Koblitz, Koblitz, and Menezes address this well in
"Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift",
ia.cr/2008/390, anotherlook.ca [KKM].  The authors have early experience in
promoting ECC, including co-inventing ECC, and finding the MOV
pairing-based attack (related to index calculus). Their general perspective
also merits consideration for future decisions.

My 2c: I too think ECDH is overall less risky than traditional DH.  As
evidence, I'd consider index calculus on traditional DH, failure of
Silverman's xedni calculus, security proof under Shoup's generic group
model, lack of faster-than-generic ECDLP algorithms (for almost all
curves), success efforts towards faster ECDLP such as the MOV attack on
special curves (showing that people have been studying ECDLP), and recent
advances in index calculus, include quasi-poly-time, on traditional DH.
Yet, surely, other pragmatic reasons, not just the ideal reason of
security, have also contributed to ECDH's adoption. Of course, I hope that
all cryptography decisions aim for security.

// Technical points about different curves in ECDH

D. J. Bernstein writes:

> Taking prime fields eliminates any attacks that exploit extra
> subfields, including any risk from FFS.  Taking large field
> discriminants avoids any risk from further automorphisms.

I agree that prime-field and "large" discriminant ECDH is less risky than
various alternative forms of ECDH.  This is the conventional wisdom.
Nonetheless, I'd hope for more clarity on:

1) the level of risk difference,

2) specific rationale for the relative risk assessment,

On 1) risk difference, I quote [KKM, Sec. 11, p.30]: "Rather, our point is
that conventional wisdom may turn out to be wrong and that, as far as
anyone knows, either choice has risks. The decision about what kind of
curve to use in ECC is a subjective one based on the user's best guess
about future vulnerabilities."  So, they argue that the risk difference is
not so clear.

My 2c: I've also proposed using a hybrid 2 or more (diverse) curves ECC
when the extra cost can be afforded (e.g. when hybridized with PQC, etc.).
My rationale was that the absolute risk may be high enough to warrant this
in some settings (though not sure how many IETF applications would warrant
this), while risk difference seemed low enough to gain from the diversity.
So, I don't see the risk difference as great.  To be clear, my view
involves guesswork.

On 2) specific rationale about the greater risk of low-discriminant curves:

a) [KKM, Sec. 11] cite some rationale to the contrary of conventional
wisdom.

b) Miller's 1985 CRYPTO proposal for ECC including special curves (with
small discriminant), with equation y^2=x^3+ax. Miller predicted it might
not be "prudent" to use these special curves. This may be the first
instance of the "conventional wisdom".

Later, the MOV pairing-based attack knocked out these curves, for the
primes that Miller proposed, so Miller's prediction was exactly right. But,
by changing the primes used, the MOV pairing-based attack is avoided.  So,
a low discriminant is not sufficient for the MOV pairing-based attack to
work.

Does there hold a general correlation between discriminant size and the
availability of a pairing needed for a MOV-type attack?  If so, is that the
specific rationale for deeming greater risk of small-discriminant curves?

c) Several people have proposed using special-form prime fields, for their
greater efficiency over random prime fields.  (The NIST curves and
Curve25519 use special-form fields.)

Conventional wisdom seems to be that using special-form field does not
increase risk (although Brainpool is an exception). I agree with this
conventional wisdom, despite the fact that MOV pairing-based attack depends
on the field, not just the curve equation, which is a point on which I
remain a little puzzled.

Note that GLV proposed using low-discriminant special-equation curves for
their greater efficiency, by way of efficient endomorphisms.

So, how much and why is using a special-form field in ECDH less risky than
using a special-equation low-discriminant curve in ECDH? Maybe there is a
good rationale, e.g. quantified correlations, etc.  If not, then why not
use a faster low-discriminant curve for the same reason we use a faster
special-form field?

// Pedantic quibbles on wording

> Taking large field discriminants avoids any risk from further
> automorphisms.

To be clear, before discussing my quibbles, I think I get the drift of the
sentence, and I appreciate that brevity was being used, and it was only a
quick email, not an academically precise paper.  Also, it's likely that my
own wording has even more issues to quibble about.  In writing this, I also
realized that my own understanding of ECC is far from thorough enough, so I
had to motivate most of my quibbles through some technical questions.


i) As to "avoid any risk".  Is this claiming that the risk of the preferred
alternative is lower?

Otherwise, it seems almost a vacuous tautology (no X => no risks from X).
So, I've been presuming that "avoid any risk" is meant to imply that the
preferred alternative (prime-field large-discriminant) has lower risk.  But
maybe my presumption is missing something.  Have I misinterpreted?


ii) As to "large".  Does this mean "typically large" or "especially large"?

If I recall correctly, isn't the typical or average discriminant size of a
random curve over p somewhere close to p or p/2.  So, I think the intended
point in saying "large" was to choose a curve whose discriminant was in the
typical size range, as opposed to the small size range, e.g. < 1000.


iii) As to "automorphism".  Should this have been "efficient endomorphism"?

If I understand correctly, for "automorphisms" in the algebraic geometry
sense, prime-field curves always have 2 or 4 automorphisms. A curve has 4
automorphism only if it has j-invariant j=0 or j=1728. In particular, many
curves with small discriminants have just 2 automorphisms, just like any
large discriminant curves.

If I recall correctly, for "automorphism" in the abstract group sense,
which depends on the group isomorphism type (i.e. a product of cyclic
groups), the number of automorphism (e.g. phi(n) if the curve group is
cyclic of size n) is not known to be correlated with the size of the curve
discriminant.  But maybe I'm wrong.

For the two reasons above, I presume you meant "endomorphism" not
"automorphism".  I speculate that this was just a typo, made in haste,
being busy with various other important things.

If I understand correctly, every curve over a prime-field has complex
multiplication. This means that all such curves have "further"
endomorphisms, beyond just scalar (i.e. "real") multiplication.  But in
large-discriminant curves, the extra endomorphisms are not efficient (or
not more efficient than scalar multiplication).  Hence, my presumption is
that you meant "efficient endomorphism", not just "endomorphism".

Best regards,

Dan