[curves] Mutual-auth Ace (was Re: MQV)

[Robert Ransom]

On 5/15/14, Robert Ransom <rransom.8774 at gmail.com> wrote:

> A sane implementation of multi-exponentiation with N bases will take
> at most N/2 times the amount of time that a multi-exponentiation with
> 2 bases does, for small values of N.  (With Straus's algorithm on a
> ‘large’ (smartphone-class) processor, the cost will increase
> non-linearly when the total table size approaches the processor's
> cache size, but it should stay linear for N up to 4.

Argh.  The cost of table lookups and additions will be roughly linear
in N until the table overflows the cache; the point of using Straus's
algorithm is that the doublings are shared, so their total cost is
independent of N.

>  With the
> Montgomery ladder on a constrained processor, the cost is roughly
> linear, but the final coordinate inversion is shared across the
> operation.)

Here the cost is closer to linear: N ladders with point recovery and
N-1 additions, then the inversion.


Robert Ransom