Elligator Square

ellsq.md

Here were some concerns I previously had about the Elligator Squared implementation in secp256k1, that are no longer concerns now:

Curve points without preimages

Here's a situation we want to avoid:

• Lots of curve points P wouldn't have preimages (u, v) with f(u) + f(v) = P
• A lot of those curve points WOULD have preimages (u, v) with f(u) + f(v) = infinity, f(u) = P
• As a result, the modified encoding would produce a non-negligibly large fraction of outputs (u, v) with f(u) = -f(v), which would be insecure

(e.g. the Elligator Squared paper did say "On inputs P that have no preimage under f⊗2 , Algorithm 1 does not terminate.")

Fortunately, we do not need to worry about this situation because the choice of f hits 9/16 of all curve points—so for any P, even in the worst case you would still have about n/8 preimages. (As u varies over all possibilities, we hit 9/16 of the curve points Q = P - f(u). At most 7/16 of the Q won't have preimages, so the remaining 2/16 would.)

Statistical distance after handling infinity

We want to make sure that the distribution of encodings (u, v) produced by the implementation in this PR is statistically indistinguishable from a uniform distribution over pairs of field elements.

Let D1 be the uniform distribution on pairs (u, v)
Let D2 be the distribution you get by
    (i) sampling a uniformly random curve point
    (ii) sampling a uniformly random preimage (u, v) under the tensor square map f⊗2
Let D3 be the same as D2, except in (i) you exclude the point at infinity
Let D4 be the same as D3, except in (ii) you use the modified tensor square map g⊗2 where:
    g⊗2(u, v) = f(u)      if f(u) + f(v) = infinity
              = f⊗2(u, v) otherwise

Note that:
- D2 is what's described in the Elligator Squared paper
- D4 is what's implemented in this PR

To show that this implementation is secure, we need to show Δ(D1, D4) is negligible
    Δ(D1, D4) <= Δ(D1, D2) + Δ(D2, D3) + Δ(D3, D4) by the triangle inequality
    Δ(D1, D2) is negligible by the Elligator Squared paper
    The arguments for Δ(D2, D3) and Δ(D3, D4) are given below

Note that the arguments for Δ(D2, D3) and Δ(D3, D4) both use the following result from the "Cryptographic Protocols" lecture notes: