The notion of principal square root is wrong

[LoupVaillant]

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.

[fscoto]

I agree with changing “principal square root” in principle (and I'd like to note that seems to be the convention in the code, too). To clarify: Do you mean “positive number” or just “non-negative” number? Considering that 0 is not considered positive for some people/contexts, it may be useful to use “non-negative” where you mean “this also works on 0”.

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.

What inverse square root routine are you looking at, exactly? I don't follow.

[LoupVaillant]

Do you mean “positive number” or just “non-negative” number?

Non-negative. I personally include zero among positive numbers (and exclude it from the strictly positive numbers).

it may be useful to use “non-negative” where you mean “this also works on 0”.

I'd rather avoid the double negation, and say "positive or zero" instead. Point taken though.

What inverse square root routine are you looking at, exactly?

The file src/p448/f_arithmetic.c in my copy of libdecaf has the isr() function. That's the one. I checked that it computes the inverse square root with a single exponentiation, and does not modify its sign. What it does conforms to what the Elligator paper suggests about principal square roots.

[fscoto]

If it helps, I-D.draft-irtf-cfrg-ristretto255-decaf448-00 specifies SQRT_RATIO_M1 and Mike Hamburg, Ph.D., contributes to that one. Elligator's unspecified, but the one-way map there is something similar in idea to the Elligator direct map.

[LoupVaillant]

Hmm, he has an abs() function even for Curve448, which suggests he does not uses the notion of principal square root.

Which would make a lot of sense with respect to not only EdDSA convention (where the sign is based on parity), but also the Elligator reverse map, which depends on the sign of the v coordinate. If the sign of a field element depended on whether it was a square, you'd need a whole exponentiation to test it!

Looking back at the paper, it says that for _p__≡3(mod_4), we could take the principal square root as a square root function, but it does not warn about the costs of doing so for the reverse map. Now that I think of it, principal square roots are a bad idea, we should use something like parity instead. Mike Hamburg very likely did use parity.

If and when I confirm that Elligator mappings for Curve448 do use parity as a sign instead of principal square roots, I propose that we scrap principal square roots entirely from our explanation. That would remove this piece of jargon, and discourage principal square roots. (We can word things in such a way that principal square root would still be a valid choice, though.)

SQRT_RATIO_M1 is one very interesting function. Not one I'd want to use as a basis for everything, but if I could implement it from invsqrt(), it might simplify the optimised code of the map and inverse map.