Question related to hiding encoding of a Curve25519 point of prime order

[weikengchen]

I have a minor question from the talk related to the hiding encoding of a point.

1. PURB uses Kyber v2, which samples the public key in the prime-order group (i.e., clearing the cofactor h = 8), instead of any random point on Curve25519.
   https://github.com/dedis/kyber/blob/v2/group/curve25519/curve.go#L84

2. The type-2 elligator converts any point on Curve25519 to a number in F_q.

I wonder if one could distinguish PURB's encryption traffic, by leveraging the insight that all the decoding of Hiding(g^x) would be a point in that prime-order subgroup, which happens only at a chance of 1/8.

There are a few ways to fix it though. First, it seems that CDH suffices so it does not need to be in the prime-order group. Second, one could sample a random point on Curve25519 and perform a hiding encoding on it, while the recipient is the one in charge of removing the cofactor after decoding. Third, curves with cofactor h = 1, though much less efficient, are always an option, e.g., BN curves, and they have some forms of elligators as well.

[nikirill]

Hi Weikeng,
I think that you are right here, an attacker indeed can get a distinguishing advantage this way. Thanks for catching this! It is true that PURBs require only gap-CDH so the prime-order group does not seem needed. I will investigate a bit more and add a fix to that.