Re: [Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages

[Samuel Neves <[e-mail]>]

On 04-01-2014 21:47, David Jacobson wrote:
> On 1/4/14 9:18 AM, Trevor Perrin wrote:
>> Another important issue, particularly for EC protocols, is to
>> distinguish operations with a fixed base (or fixed point) from
>> operations with a random base / point. The fixed operations can be
>> optimized to be several times faster (perhaps ~4x is a rule of thumb
>> I've heard).
> This seems strange to me, and I've implemented ECC several times over
> the last decade.   I think you might have meant that implementations
> using special modulii that can be written as  the sum of  +/- 1 at
> selected word boundaries or as 2^n - k for some small k are several
> times faster than implementations written to support arbitrary moduli.

Fixed base lets you precompute arbitrary multiples of G offline. For
example, if you compute {0..16} G, 2^4 * {0..16} G, 2^(4i) {0..16} G,
..., you only need to perform around log2(exponent)/4 online group
operations. Doing this safely against side-channel attacks requires some
care, of  course.