potential optimization for Edwards to Montgomery map

[kwantam]

Michael Scott wrote to observe that the generic Edwards to Montgomery map can be simplified in some cases.

Consider the Edwards curve

a * v^2 + w^2 = 1 + d * v^2 * w^2

Assuming that there is no corresponding standardized Montgomery curve, the document currently suggests mapping to the following curve

K * t^2 = s^3 + J * s^2 + s
J = 2 * (a + d) / (a - d)
K = 4 / (a - d)

and then mapping back to the Edwards curve via

v = s / t
w = (s - 1) / (s + 1)

The j-invariant of a Montgomery curve depends only on the J coefficient, meaning that for all Montgomery curves given above, the curve

t^2 = s^3 + J * s^2 + s

is isomorphic to either the curve or its quadratic twist. Most interestingly, to us, when K is a quadratic residue, then the above two Montgomery curves are isomorphic via

(s, t) ↦ (s, t √K)

and therefore we can map back from the curve with K = 1 to the Edwards curve via

v = (s √K) / t
w = (s - 1) / (s + 1)

Note that this is exactly the map that RFC7748 specifies from edwards25519 to curve25519.

(See https://eprint.iacr.org/2017/212.pdf for more info on the above.)

---

Along the same lines, when K is non-square we could map from

Z * t^2 = s^3 + J * s^2 + s

to the Edwards curve, where Z is the distinguished non-square in F used to map to Montgomery. The Montgomery to Edwards map would then be

v = (s √(K/Z)) / t
w = (s - 1) / (s + 1)

The advantage is that this lets us use a very small value (Z) in place of K (which is likely much larger) when evaluating Elligator.

---

OK, so what does this mean to us? It means that we can, in principle, specify a somewhat better optimized map from Edwards to Montgomery. In particular, keeping the definitions above,

if is_square(K):
    // map from t^2 = s^3 + J * s^2 + s
else:
    // map from Z * t^2 = s^3 + J * s^2 + s

So: question: do we think this is would be a reasonable optimization to add?

[kwantam]

My two cents: the difference in cost among these options is pretty well spelled out in the latest optimized pseudocode. That difference is not huge---a few multiplications. So the upside is in my mind somewhat limited.

On the other hand, the downside is that we're adding additional complexity to the document. It's not a ton of complexity, but we have a lot of opportunities to add small extra bits of complexity and we've done a good job recently of avoiding them. I'm generally in favor of continuing that trend.

(edit to add:)

The other upside of this change is that it eliminates the special case for edwards25519. Unfortunately, we still need a special case for edwards448. If it eliminated both I'd probably be more excited to make this change...

[kwantam]

(cc @armfazh @chris-wood)

[chris-wood]

I'm not inclined to take this change. Folks such as MIRACL and RELIC can implement it if they like, though pushing that complexity into the document feels like it'd do more harm than good. (We probably need to go through and ruthlessly trim unnecessary optimizations in the future before shipping, anyway.)

[armfazh]

Agree with you. Nice trick indeed.

[kwantam]

Here's an alternative: since the rational map is part of the suite definition, we don't have to make the generic mapping a MUST. Instead, we can make it a SHOULD, and add an appendix that spells out the optimized alternative. I'll write this up and we can decide whether we want to include it or not.

[kwantam]

Thoughts on #244 @armfazh @chris-wood ?

[armfazh]

PR:244 was merged, so this can be closed.

[kwantam]

agree with @armfazh: seems like whichever way we decide on #246, we can close this