[Cfrg] draft-irtf-cfrg-hash-to-curve // More efficient method available for elligator2

["Björn Haase" <[e-mail]>]

Hello to all, I hope that via this list I might be able also to reach the contributors of the

draft-irtf-cfrg-hash-to-curve draft at github

 

https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/master/draft-irtf-cfrg-hash-to-curve.md

 

over this list.

 

Regarding the Elligator 2 map, the algorithm shown in the  github version of the draft is actually slower than necessary. It requires two exponentiations (for one inverse and one square root).

 

Some time ago Mike Hamburg did point me to a solution on how to implement this with one single exponentiation. The algorithm is found also somewhere hidden within the Ed25519 paper of Bernstein, Duif, Lange, Schwabe and Yang. Still Benoît and me did consider it helpful to write down the faster algorithm explicitly in our last paper, because we thought that there might be others that missed this optimization opportunity :-).

 

You'll find the explicit write-down in section 8.2 on page 33 of

 

https://tches.iacr.org/index.php/TCHES/article/view/7384

 

Yours,

 

Björn