Re: [Cfrg] How to (pre-)compute a ladder [full C implementation]

[Francisco Rodriguez- Henriquez <[e-mail]>]

Dear CFRG community,

We would like to share with you a full C implementation of the 
ladder procedure described in the IACR pre-print 2017/264:

        "How to (pre-)compute a ladder"

The C code can be downloaded from,
https://github.com/armfazh/rfc7748_precomputed

We are reporting the following benchmarked timings for 64-bit Intel 
architectures (table entries are given in clock cycles),


X25519 				Haswell 	Skylake
proposed Keygen rtl ladder	 90,895 	 72,571
Shared secret 	 		138,962 	107,942
S.Secret/Keygen speedup		  1.529	          1.487
overall D-H speedup               1.209           1.196


X448				Haswell 	Skylake
Proposed Keygen rtl Ladder	401,902 	322,040
Shared Secret 			670,747 	528,470
S.Secret/Keygen speedup           1.668           1.641
overall D-H speedup               1.251           1.243

Notes:

+ The Key generation reported above was computed using the proposed
   right-to-left ladder
+ The Shared secret was computed using the procedure described in the RFC
   7748 memo
+ The D-H speedup is obtained as the ratio,
 		2*shared secret / (shared secret + key generation);
+ In the sense explained in our pre-print, our procedure fully complies
   with the RFC 7748 memo.

With best regards,
Thomaz Oliveira, Julio López, Hüseyin Hisil, Armando Faz-Hernández and 
Francisco Rodríguez-Henríquez


On Thu, 11 May 2017, 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