Add Elligator Square module #982

Based on #979.

This adds a module with an implementation of the Elligator Squared algorithm for encoding/decoding public keys in uniformly random byte arrays.

tACK 7b1e6260e215174561a2d1fdd7f500ba6eaf1489

I'll give a full ack once I carefully review:

• Optimizations in section 3 of the writeup
• Low-level implementation
• Argument that the encoding is statistically indistinguishable from 64 random bytes, even with the minor changes (e.g. point at infinity, omitting some duplicate checks)

Basic question, what would go wrong if we use naive approaches such as:

(1) Given a random curve point (x1, y1), increment the x coordinate until you get another curve point (x2, y2). Use a random field element in [x1, x2) as the encoding. Decode by decrementing until you get an x corresponding to a curve point.

(2) Just generate and use a random field element as the encoding; both parties decrement x until they get a valid curve point.

I'm guessing the reason we don't do something like that is (1) will produce field elements that don't look random, and (2) will generate keys in a biased way?

@robot-dreams:

(1) Indeed, this will result in biased encodings, because the distance between field elements which are valid X coordinates varies, and attacker-known, so they can detect a bias: encodings for which the previous and next valid X coordinate are close together will occur more frequently.

(2) Biased private key isn't really a problem as long as (a) the bias is small and (b) the bias isn't recognizable from the encodings/public keys, which is the case here. There is another problem however: the encoder wouldn't know the corresponding private key.

Oops, good point about (2), I am silly. 🤣

But about (1), if there were a known upper bound on the distance between valid X coordinates (AFAIK there isn't one, but more than ~128 is probably negligibly rare), you could actually use f(x) = (first point with largest X coordinate not larger than x) as mapping function in the scheme. I suspect that's significantly slower than what we have now though, as you'd need avg 128 iterations, and counting the distance between valid X coordinates around each...

Code Review ACK 7b1e6260e215174561a2d1fdd7f500ba6eaf1489, modulo verifying the proof that the encoding is actually indistinguishable from 64 random bytes

I opened the different implementations of f, r side by side and checked that:

• Section 2.6 is equivalent to Section 3
• Section 3 is equivalent to the broken-down Sage implementation
• The C and Sage implementations are equivalent

Basic question:

• The use of SHA256 for generating branch values seems reasonable, but just wondering, is there a justification that this use of SHA256 gives you a secure PRG (taking rnd32 as the key)? (Is this a well-known construction?)

ACK 7b1e6260e215174561a2d1fdd7f500ba6eaf1489, I don't think the rest of my comments are blocking.

• I'm happy with the argument that the sampling algorithm produces a uniformly random preimage of a curve point
• Although I wasn't yet able to calculate the exact statistical distance between the distribution implemented here and the distribution described in the paper (handling infinity being the only difference), I suspect that it's O(1/p), i.e. negligible unless I made a big mistake in my estimation.
• I've convinced myself (in part with the help of the section starting with "Back to Delphia" in this article) that the use of SHA256 to generate random branches / field elements is secure under a random oracle model 😅 sipa's favorite! Here, an attacker would have no choice but to guess rnd32.

The only thing I haven't verified is that the function f is indeed "well-distributed", but I don't want to block this PR until I've learned the background material needed to check that—I'm happy to accept that without verifying the proof for now.

Finally, would it make sense to either:

1. Elaborate on the statement not terribly non-uniform in https://github.com/sipa/writeups/tree/main/elligator-square-for-bn#25-dealing-with-infinity
2. Make the encoder NOT target the f(u) = -f(v) case, so that it's really easy to show that the statistical distance between the implemented distribution and the one in the paper is neglible (the decoder can still handle that case, so that every 64-byte string decodes to a valid public key)

Elaborate on the statement not terribly non-uniform in https://github.com/sipa/writeups/tree/main/elligator-square-for-bn#25-dealing-with-infinity

I should drop that, as it's confusing. Given the immensely low probability of hitting infinity in the first place, how it is handled is totally irrelevant.

This comment aims to indicate that it's better than e.g. mapping infinity to the generator or so (which it is, as it'd mean the generator has ~2n ellsq preimages, while other points only have ~n), but I don't think that's a useful justification given it's only changing an negligibly frequent event anyway. The real justification is: it's probably the easiest way to implement this edge case.

Make the encoder NOT target the f(u) = -f(v) case, so that it's really easy to show that the statistical distance between the implemented distribution and the one in the paper is neglible (the decoder can still handle that case, so that every 64-byte string decodes to a valid public key)

I don't think it should be hard to show the difference is negligible, given the fact that even triggering (much less observing) a case in which the outcome is different is negligible (it requires picking a uniformly random u for which f(u)=-P).

OK, I'm fully on board with this now! If you're curious, see https://gist.github.com/robot-dreams/86302bfca28bf9dc83ced365cd428f64 for way too much detail that nobody needed or asked for.

ACK 07a4ef5a08cea9916cf93603670d8ee4d5340540

Rebased.

ACK f997dadf592131054d1cfca6175730e53dee52a1 (aside from most recent build / CI changes) based on:

• #982 (comment)
• git range-diff 0a40a4861ae654b3685d3d3670d45876f7cc9c48 07a4ef5a08cea9916cf93603670d8ee4d5340540 f997dadf592131054d1cfca6175730e53dee52a1

Mental note: simplify this after #1033.

Closing, as Elligator Square seems strictly inferior in performance and complexity to ElligatorSwift.