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

[Joe]

On 6/24/21 1:30 AM, Joe wrote:
> You probably want a PRP (or key-wide block cipher) to avoid scenarios 
> where flipping individual bits lead to weird corner cases. At the very 
> least an attacker could structure their key such that e.g. two guesses 
> would decode to related keys, which weakens the properties of your EKE 
> PAKE ever so slightly (no longer one guess per interaction).
> 

Sorry, I was tired and mixing up threat models.

With XOR the biggest problem as I see it is MITM with deterministic bit 
flipping, where targeting related keys could lead to a key confirmation 
attack (if Alice & Bob pair successfully with a bit-flipped key, you 
know your bitflip resulted in a related key). I'm not sure how practical 
that is, you or Mike are probably better situated to answer that.

The precomputation stuff is a separate issue that is relevant for 
encoding schemes like UniformDH and Elligator/Elligator2/Elligator^2 
where several encodings lead to the same or related keys upon decoding.

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 Squared [2] was written by Mehdi Tibouchi.

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

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

[1] https://elligator.cr.yp.to/papers.html
[2] https://ifca.ai/pub/fc14/paper_25.pdf
[3] https://eprint.iacr.org/2014/486.pdf
[4] https://github.com/LoupVaillant/Monocypher