loupvaillant/elligator

Mirror of a website on Elligator by Daniel J. Bernstein, Mike Hamburg, Anna Krasnova, and Tanja Lange

elligator's Issues

Layout seems to avoid placing the nav flexbox on the side

This doesn't happen on https://monocypher.org/ on which I based this. This requires closer investigation.

Choice of name for curve point coordinates

Currently, the text uses x and y to denote the coordinates of a curve point. This is in line with the original Elligator paper, earlier DJB paper on Curve25519, and the Ref10 source code. (Heck, even Monocypher kept that convention.)

The problem with that choice is that convention has since changed. RFCs now tend to refer to Montgomery curve point coordinates as (u, v) instead. I believe they do this to prevent ambiguities with (twisted) Edwards curves, for which they still use (x, y).

I'm personally inclined to follow the most recent convention for the sake of it. More importantly though, we actually Edwards curves to speed up the procedure involving the inverse map. Well need to show the (x, y) to (u, v) conversion at some point, or at least the extended coordinate variant. (And now I don't know what to do about Z, which is now used 3 times: Montgomery extended, Edwards extended, and the non-square. We'll address that later, perhaps…)

I'll do the edit, but I want to make sure we agree on the convention to begin with.

Incompatibilities

The TODO still requires a page outlining incompatibilities between libsodium, I-D.draft-irtf-cfrg-hash-to-curve, Monocypher and Kleshni's implementation.

Test vectors

It is necessary to add a page containing test vectors as well. For Curve25519, a lot of the heavy lifting can be done just by instrumenting the existing test suite in Monocypher. For Curve448, said test suite will need to be adapted.

Licensing

The question of licensing the website came up in discussions. This needs to be decided upon and applied; “no license” is a valid option as well.

Choice of character to denote multiplication

Currently, multiplication is denoted by the "·" (mid point) character. It took me a while to pick up on that, and expect readers to be equally puzzled. My first instinct is that I don't like this choice, and would like to propose two other alternatives:

• The "×" character (don't know if it has an HTML markup for it), which most people will understand means multiplication without needing to be explained.
• Nothing at all, following established mathematical convention, but perhaps might hurt readability for programmers. It's still workable if we stick to one letter variables, but I don't like the syntactic ambiguity with function calls (which admittedly only happens with the legendre symbol.

If there's a justification for using the mid point that I'd miss, I'd be willing to keep it, but then we should add a quick note that explains what it means.

The notion of principal square root is wrong

A more careful reading of the Elligator paper revealed that my understanding of the notion of the principal square root was not correct. I believed the notion was somewhat arbitrary, and it turns out that it may not be.

• On prime fields GF(p) where p ≡ 3 (mod 4), the paper defines the principal square root of some number a as the unique square root of a that is also a square. We know it's unique because -1 is not a square in those fields (recall that when you multiply two non-squares together, you get a square).

• On prime fields GF(p) where p ≡ 1 (mod 4), we don't have such a neat option, so we have to partition the field in some arbitrary way (provided negation still makes sense).

• On real numbers, the principal square root is simply the root that's positive. Note that it's also the root that has a square root (only positive numbers have a square root), so we can see why the Elligator paper went with its definition.

Currently, we described the set of principal square roots as if it was some arbitrary parameter. That may actually be an error on two fronts: first, the notion may be not as arbitrary as I thought it was, while the notion of positive number definitely is (see how Ed25519 and the Elligator paper made different choices). Second, "principal square root" is really opaque jargon, whereas "positive number" should trigger the right intuitions in most readers right away.

So I propose that we modify the explanations by basically swapping "principal square root" and "positive number". We must decide on the set of positive numbers. When p ≡ 1 (mod 4) an obvious choice is the set of principal square root. For other primes, we chose the set of even numbers or [0: (p-1)/2]. Then we stop talking about principal square roots altogether, and only speak of positive numbers.

First though, I want to confirm that Elligator for Curve448 does indeed use principal square roots. So far, its inverse square root routine seems to confirm this. I need to confirm this by looking at the inverse map.

Decaf/Ristretto

We still need to figure out and describe how to use Elligator with Decaf/Ristretto. The Ristretto website and I-D.draft-irtf-cfrg-ristretto255-decaf448-00 specify a “one-way map”, so perhaps this is necessarily unidirectional.

Maybe add a page for Hash to curve?

Why we might want to add that page:

• Elligator's original use case notwithstanding, it seems most of the effort goes to map-to-curve and hash-to-curve. See Libsodium, Dalek, and the RFC draft.
• Map-to-curve and hash-to-curve do more than just apply the direct map, we might want to explain what goes there.

Why we might want to hold our horses:

• The relevant RFC is still a draft.