Re: [Cfrg] How to (pre-)compute a ladder [revised version]

[Antonio Sanso <[e-mail]>]

hi Peter
On Jun 16, 2017, at 6:58 AM, Peter Dettman <[e-mail]> wrote:

> Hi Francisco,
> 
> I've updated my (java) implementations of X25519 and X448 in line with
> your revised paper.

out of curiosity is this a public repo I can look at ? :)

regards

antonio

> My rough benchmark results for a complete ECDH are
> -17.7% and -19.5% time required for X25519 and X448 respectively.
> 
> These are perhaps slightly more modest than the paper's estimates. Your
> paper already anticipates that (uncounted) field add/sub are significant
> in practice.
> 
> Part of the difference however is that my implementation of Algorithm 3
> handles the final 'q' bits using simple doublings, and removes redundant
> cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented
> in RFC 7748, but it might be a fairer comparison to first apply to Alg.
> 3 those of your optimizations that are applicable.
> 
> Also, my (32-bit) X448 implementation (Alg. 5) required a carry
> propagation for 'A' (line 10), due to tight bounds on limbs when
> squaring D, E. I did the same for (32-bit) X25519 although I haven't yet
> proved it necessary.
> 
> An idea: for fixed-base X25519, why not precompute one doubling? i.e.
> just calculate (k/2) * 2P, needing only 2 final doublings (you even
> already have S of order 4). I am not sure whether this extends to
> precomputing (q-1) doublings.
> 
> Another thought that occurred to me is that someone might get the idea
> to use your fixed-base ladder with some other point. Couldn't this go
> awry if that point were already "P + S" or similar? If so, a caution
> somewhere in the paper on preconditions for the fixed point might be
> advised.
> 
> Regards,
> Pete Dettman
> 
> 
> On 12/05/2017 7:14 AM, Francisco Rodriguez- Henriquez wrote:
>> Dear CFRG community,
>> 
>> We would like to draw your attention to an improved version of our IACR
>> pre-print 2017/264 now entitled:
>> 
>>    "How to (pre-)compute a ladder"
>> 
>> In this revised version, we present an improved differential addition
>> formula that uses pre-computation to match the computational cost of the
>> classical Montgomery differential addition.
>> 
>> Accordingly, our estimates suggest that a full implementation of our
>> pre-computable ladder proposal should outperform state-of-the-art
>> software implementations of the X25519 and X448 functions by a 40%
>> speedup when working in the fixed-point scenario.
>> 
>> We would be delighted to receive feedback (including sightings of typos)
>> from the CFRG community.
>> 
>> With best regards,
>> 
>> Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco
>> Rodríguez-Henríquez
>> 
>> 
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg