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

Mike Hamburg mike at shiftleft.org
Tue Jun 22 12:14:01 PDT 2021

Hi Trevor,

I think it’s elligator squared, yeah.  In the ROM, you can probably replace the first component with the hash of a smaller number of random bytes.  I’m not sure on the statistics there in general, but if the point you’re hashing is random then as few as 2 bytes might suffice (needs proof though).

I’m wary of xoring with the hash of the password.  I don’t see an obvious attack on it, but I suspect that to prove security of EKE you need an ideal cipher, not just xor.  If you expand the first component of elligator squared from a hash, then by hashing the password into that, you should get one of the PAK variants.  Of course, you’d again have to prove that it’s not only a secure PAKE, but also indistinguishable from random.

— Mike

> On Jun 22, 2021, at 6:04 PM, Trevor Perrin <trevp at trevp.net> wrote:
> Hi,
> Does anyone know the state-of-the-art for encoding/decoding an
> elliptic curve point into a random-looking bit string, such that the
> mapping covers all points and bit strings?  Is it Elligator-squared?
> https://eprint.iacr.org/2014/043.pdf
> I'm interested in this partly as a way of making handshake protocols
> (e.g. Noise) indistinguishable from random (e.g. censorship
> resistance).
> Also if such a protocol was encoding its ephemeral DH public keys in
> this form, I believe (?) this would enable a PAKE almost for free:
> simply XOR the encoded DH ephemeral public values (or even just one of
> them) with the password or hash(password), per Bellovin and Merrit's
> 1992 EKE paper:
> https://www.cs.columbia.edu/~smb/papers/neke.pdf
> ?
> Trevor
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves

More information about the Curves mailing list