[curves] Choosing an extra-strength curve

[Diego Aranha]

> Do you think 2x slower is accurate?  (Or do you have performance
> numbers on Brainpool or similar curves I could add to the spreadsheet
> [3])?
>

This is accurate for a modular multiplication:

- A generic random prime would require something like Montgomery reduction,
which has quadratic complexity (but a little higher than the multiplication
part, actually, due to a linear overhead).

- A special prime usually has faster reduction with linear complexity.

As a concrete example, our pairing code in Sandy Bridge had 60 cycles for
the multiplication part and 100 cycles for the modular reduction at some
point. If a special prime would give us a modular reduction in 10-20
cycles, the ratio would be approximately 2. Assuming that modular
multiplication is the performance-critical operation for ECC, which should
be the case for sane implementations, then the ratio is approximately 2.
Notice however that additions are becoming significant in recent hardware
due to faster integer multipliers (specially for pairing computation), but
not enough to change this considerably.
--
Diego de Freitas Aranha
Institute of Computing - University of Campinas
http://www.ic.unicamp.br/~dfaranha


On Tue, May 6, 2014 at 2:15 PM, Johannes Merkle <johannes.merkle at secunet.com
> wrote:

>
> > I do not think random primes are worth it. Looking at the past, the SNFS
> is not *that* great of an improvement. Of
> > course it matters in practice, and special >1024-bit numbers are
> factored whereas the best general result is RSA-768.
> > However, it (asymptotically) 'only' shaves around 20 bits of security
> off of RSA-2048 (~112-bit security), and 50 bits
> > off of RSA-15360 (~256-bit security).
> >
> > Suppose there is indeed some similar speedup for prime-field elliptic
> curves, along with some index-calculus type
> > attack. Firstly, if the attack is subexponential, current sizes are dead
> regardless of the parameters. Secondly, as
> > Trevor mentions, how many extra bits in the prime field could we buy
> with the 2x slowdown of random primes? 64? 128? It
> > seems to me that a slightly bigger special prime would be a better
> tradeoff than a random one, all things considered.
>
> Yes, the specific speed-up provided by the SNFS over the GNFS might
> compensate the increase in bit length suggested by
> Trevor. But I referred to the SNFS just to illustrate that special primes
> can in principle help to improve or to
> leverage attacks, i.e. it was a qualitative comparison, not a
> quantitative. Nobody knows if and how much a certain
> structure might help attacks, and extrapolations from finite field DL or
> integer factorization to ECDL are hardly possible.
>
> That said, let me make clear that I do not think that future attacks on
> special prime curves are at all likely to occur.
> Still, they are conceivable, at least for me.
>
> >
> > There are also other kinds of structure to consider beyond the primes
> (which seem to presently be very low-risk). One
> > example of structure could be small even cofactors, which are known to
> speed up index calculus over extension fields in
> > some cases [1]. None of this affects elliptic curves over prime fields,
> but it still seems more realistic of a threat
> > than special primes.
> >
>
> I agree that this aspect should also be considered. However, I don't dare
> to assess which threat is more realistic.
>
> We should try to avoid any unnecessary structure for a conservative set of
> curves.
>
>
> --
> Johannes
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140506/95fb32bc/attachment.html>