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

Thanks for the pointer, Björn! I filed [1] to track this issue.

Best,
Chris

[1] https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/issues/133

On Tue, Jun 18, 2019, at 11:40 AM, "Björn Haase" wrote:
> 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
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>