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

[Trevor Perrin]

On Wed, Jun 23, 2021 at 4:43 PM Joe <joe at celo.io> wrote:
>
> 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).


Trying to write down security goals for a simplified EKE:

  Alice -> Bob: Encrypt(password, Encode(g^a))
  Alice <- Bob: g^b, Hash(g^ab)

where Hash() is modelled as a random oracle, and Hash(g^ab) provides
key confirmation.

Something like this?

 (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.

 (b) A malicious Bob, given any valid initial message, can't produce a
password for which the initial message fails to decrypt or decode,
because then he could rule out that password.

I think (b) is easy to check, so the risk with Encrypt()=XOR of
Hash(password) is about (a):  maybe Alice could find two DH public
values whose encodings have some XOR difference, and for which she
knows the discrete log?

If we can't rule that out via some assumption about the encoding, I
wonder what is the simplest encryption construct that rules that out.

Interesting topic, will think more...

Trevor