[curves] encoding points -> bitstrings: indistinguishability, PAKE?

[Mike Hamburg]

> On Jun 24, 2021, at 1:50 AM, Trevor Perrin <trevp at trevp.net> wrote:
> (a) A malicious Alice can't produce an initial message and two
> passwords which decode this message to two different public values
> A1=g^a1 and A2=g^a2 for which Alice knows a1 and a2; because then she
> could check two passwords against Bob's response.

I suspect that this is hard to prove for the XOR encryption, except maybe in the generic group model.  I wouldn’t trust the generic group model with Elligator as the encoding — in fact IIRC SIKE is already using non-ideal properties of an Elligator 2 variant in its point compression algorithm.


Joe wrote:
> It looks like Mike was a co-author of the Elligator 1+2 paper [1], so perhaps he can comment regarding which algorithm seems most relevant.

Elligator 2 is fine for key exchange, but note that if Trevor wants to replace points in general EC protocols, then it won’t work: it requires the ability to retry a message with different randomness if the point doesn’t encode.  For general protocols, you need an encoding that works for all points on the curve, such as Elligator Squared.  However, you can always combine them to make “Elligator 2 Squared”, which works for any curve with a point of order 2.  This has a separate proof of indifferentiability [5].

You could also use the “Elligator 2 with wallpapering” approach from that paper, but it’s not implemented as far as I know and has essentially no advantages over “Elligator 2 squared”.


> Elligator Squared [2] was written by Mehdi Tibouchi.

This would be the best choice for odd-order curves over large fields.


> Binary Elligator Squared [3] is yet another paper, I haven't looked into this one.

This is for curves over GF(2^n), which are probably not the best choice unless you have an unusual constraint.


> Loup Vaillant has an implementation of Elligator 2 in the "Monocypher" library [4], it's the only maintained implementation I've seen.

Monocypher is an impressive piece of work.  My library, libdecaf [6], also implements Elligator 2 and Elligator 2 squared.  Note that they are likely incompatible, because libdecaf targets Elligator2 at the Jacobi quartics used by the Ristretto / Decaf encodings, instead of at the Montgomery or Edwards curves.

Cheers,
— Mike

[5] https://eprint.iacr.org/2020/1513 <https://eprint.iacr.org/2020/1513>
[6] https://sourceforge.net/projects/ed448goldilocks/ <https://sourceforge.net/projects/ed448goldilocks/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20210624/da02f144/attachment.htm>