[curves] The great debate over point formats

[Diego Aranha]

On Thu, Jan 30, 2014 at 12:04 PM, Robert Ransom <rransom.8774 at gmail.com>wrote:

> On 1/30/14, Paulo S. L. M. Barreto <pbarreto at larc.usp.br> wrote:
> > Hello to all,
> >
> > On Wed Jan 29 18:07:34 PST 2014, Robert Ransom <rransom.8774 at gmail.com>
> > wrote:
> >
> >> My main problem with the 'Brazil' curves is that all of them except
> >> M-221 (even the E-* curves) have really *ugly* coordinate fields.
> >> They make the NSA fields look nice by comparison (and at least those
> >> would have the advantage of requiring less extra hardware within a
> >> TPM, as someone mentioned on one of the IETF lists
> >
> > I'm just now coming back from vacations so this message is very brief,
> but
> > you
> > got my attention. Could you please state your 'beauty' metric
> > quantitatively?
>
> Curve operations modulo a number of the form 2^b - k are easy to
> implement efficiently if there is a regular arrangement of limb sizes
> small enough that an operation of the form (a+b)*(c+d) can be
> performed without carrying the inputs to the multiplication, and with
> reduction modulo x^l - k performed during the multiplication, for both
> signed 64-bit and unsigned 128-bit multiplication-result lengths.
>

Dear Robert,

Your comments are very relevant, but let me justify some of our design
choices. We picked field sizes similar to NIST curves, trying to provide
something closer to drop-in replacements. Additionally, we considered not
only vector or hardware implementations, but also the fast integer
multipliers already available to software implementations in many
platforms. Of course, these could require specialized assembly-language
multipliers for optimal performance. You can find some brief notes below.


> * Curve3617 coordinates (mod 2^414 - 17) can be represented in four
>   reasonable ways: a uniform sequence of 9 46-bit or 18 23-bit limbs
>   (trivial to implement), two repetitions of (52,52,52,51)-bit limbs
>   (faster than the 9-limb representation), or two repetitions of
>   (26,26,26,26,26,26,26,25)-bit limbs (faster than the 18-limb
>   representation, and still (just barely) safe).  Carries are
>   vectorizable for all of these representations.
>
> * E-382 coordinates (mod 2^382 - 105) have a vectorizable 16-limb
>   representation for 32-bit processors (same shape as that for
>   Curve3617, with two fewer bits per limb), but that's as long as for

  Curve3617, and to obtain a lower security level.  Because 105 is so
>   large, even a 15-limb representation requires that reduction modulo
>   x^15 - 105 be separated from multiplication, and carries do not
>   appear to be easily vectorizable.
>

The difference in security levels is rather small, only ~16 bits, which is
less significant at the 192-bit level. However, conventional non-vectorized
implementations would be penalized by the extra limb in Curve3617. If
reduction gets too expensive, we have more room for lazy reduction.

* M-383 coordinates (mod 2^383 - 187) are worse than E-382: no obvious
>   way to vectorize carries for the 16-limb representation, and 187 is
>   even bigger than 105.
>

Similar to the above, but with less room for lazy reduction.

Best,
--
Diego de Freitas Aranha
Department of Computer Science - University of Brasília
http://www.cic.unb.br/~dfaranha
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20140131/8a77faf6/attachment-0001.html>