Subject: Re: [Crypto-panel] Request for review: "Alternative Elliptic Curve Representations"

From: Karthikeyan Bhargavan <[email-masked]>
Date: Fri, 12 Nov 2021 14:28:00 +0100

Hello All,

Below is a detailed technical review of draft-ietf-lwig-curve-representations-21 by Benjamin Smith (cc-ed).

I discussed this review with Ben and agree with his concerns and it would be great if the authors could address his questions.

In particular, I feel the code reuse motivation needs to be better justified.
One way to do this would be to extend Implementation Considerations (and/or Implementation Status) with concrete examples of code reuse in Wei25519 implementations, quantified in lines of code, for example.
If most of the code in these implementations is in the field arithmetic, which can be reused between representations anyway, the argument for this draft becomes less compelling.

Best regards,
Karthik

===
draft-ietf-lwig-curve-representations-21
===

[Curve representations draft](https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/>)

# Review by Benjamin Smith

This draft specifies a series of new elliptic curves related to Curve25519 and Curve448, and transformations between these new curves and Curve25519/Curve448.  The motivation is essentially code re-use: legacy elliptic-curve software and hardware works with the classic "short Weierstrass form", often with the a-coefficient set to -3, but in more recent protocols and software we might work with Curve25519 and Curve448 in either "Montgomery form" or "twisted Edwards form" (depending on the protocol), for efficiency reasons.  On the surface, these equation forms are not the same, so the newer curves are incompatible with legacy ECC code.

This document bridges the gap by writing down isomorphisms to short Weierstrass curves with a=-3 where such isomorphisms exist, and isogenies (homomorphic maps) where isomorphisms do not exist.  It also specifies several other curves and maps, of various levels of usefulness.

I am not entirely convinced by the code re-use argument here.  I agree that this is an interesting goal, given the time and effort it takes to develop and certify cryptographic software and especially hardware.  But for a concrete example, suppose we have an existing implementation elliptic-curve scalar multiplication on NIST P256, and we want to use this document to re-use that software for scalar multiplication on Curve25519:

1. The curve group operations for P256 can be and reused, and so can the scalar multiplication algorithm(s), insofar as they just call the curve group operations.
2. The underlying field arithmetic implementation must be rewritten/replaced, because these curves work modulo different primes.  Generally this isn't just a matter of changing a hard-coded value for the prime p: the different primes have been chosen to allow completely different optimized modular reduction algorithms.
3. The code to actually map points between the two curves must be added, and in some cases this code will be particularly large.  In particular, the code here to convert from Curve25519 to Weierstrass with a=-3 involves 9kb worth of data to define the isogeny (to say nothing of the code to evaluate the isogeny).
4. The protocol may need to be tweaked to deal with the implicit multiplication by the isogeny degree

Comparing the small amount of code saved to the new code to be added, and the possible modifications to the protocol: is this really worth it?  If you're going to have to add a whole new field arithmetic implementation _and_ an extremely heavy isogeny-evaluation function (specified by a massive collection of precomputed coefficients), then maybe you would be better off just implementing Curve25519 properly.

One might argue that the real benefit here would be for curve implementations in hardware, where changing (and re-certifying) designs is extremely slow, but I think that argument is defeated by the fact that the finite field arithmetic (the lowest level) still has to be rewritten.

Ironically, herefore, this document could be read as a convincing argument **against** code re-use.  Of course, I might just be totally missing the point. In that case, since I have read all 150 pages and still missed the point, I think this means that the author hasn't fully explained the point.

The document is _extremely_ long, and often quite repetitive.  There is too much repetition of boilerplate text blocks for the various transformations applied to different concrete instances.  To give just one example: Appendix M is essentially the same as Appendix E, but with different curve parameters.  There must be a way to minimise this repetition (especially given the focus on code re-use!).

More structural/editorial issues:

- Appendix I (data conversions) must already be covered elsewhere: it could probably be removed.
- Appendices P, and Q are basically out of scope, and should be removed.
- Appendix K is also essentially out of scope.
- Appendix L can also be removed: it is a long and unneccessary elaboration on a remark in Appendix K, and therefore out of scope.
- Appendix N seems mostly superfluous: I don't understand why this Edwards448 curve needs to be defined and named (we already have Ed448...)

Most of the technical content is uncontroversial, and it is mostly correct (detailed technical comments follow).  I am not competent to evaluate Sections 10, 11, and 12, but I have checked the rest in detail.

One key technical point: as mentioned above, the transfer between many of the curves here requires an isogeny (a homomorphic map) rather than an isomorphism (essentially a change of coordinates).  One of the most important isogenies here - the one from Curve25519 to Wei25519.-3 - has degree 47.  This means that specifying it involves, at a minimum, a degree-23 polynomial w(x).  This polynomial w(x) is dense, so we need to specify (and store) 23x 32-byte coefficients.  This obviously requires a lot of space!  I say "at a minimum", because two more polynomials, u(x) and v(x), of similar degree, are required. Mathematically they can be derived from w(x), but for algorithmic simplicity it may be more convenient to specify them in their expanded form, as is done here.  Then, the "dual" map from Wei25519.-3 back to Curve25519 has its own large u, v, and w.  Ultimately, this means a *lot* of space: 9kB of memory in code, and 12+ pages of this document.

Reducing this size (and evaluation time) is important if this is to be made practical.  I have checked, and I agree with the author that there is no isogeny of *prime* degree less than 47 from Curve25519 to a short-Weierstrass curve with a=-3.  However, there *is* such an isogeny of composite degree 46 (I could not find any lower-degree composite isogenies that do the job).  This doesn't look like much of an improvement on the surface, but the degree-46 isogeny is the composite of a degree-2 isogeny (very easy to specify/compute) and a degree-23 isogeny (roughly half the coefficients and complexity compared with the 47-isogeny).  This means that by changing the definition of Wei25519.-3 to be the codomain of the 46-isogeny instead of the 47-isogeny, the time and space required to encode and compute the isogeny will be literally cut in half.  Of course, half of 9kB is still quite expensive, and it remains to be seen if anyone will consider this practical for applications, but I think it is still an improvement that the author might want to consider using.

## Technical remarks

- "unequal to" should generally be replaced with "not equal to"
- most instances of "hereof" should be "thereof", though something less archaic than "(t)hereof" would be even better

### 1 Fostering Code Reuse with New Elliptic Curves

- `we specify these curves` should probably be a bit more specific: "we specify the CFRG curves"?

### 4 Examples

- In 4.1: `Moreover, with X25519, private keys are generated in the interval [2^251,2^252-1] rather than in the interval [1,n-1] (the so-called "clamping") and one uses as base point G':=h*G, where G, n, and h are, respectively, the fixed base point, the order of the base point, and the co-factor of the curve in question`: I think this is wrong.  The private keyspace for X25519 is $S = \{2^{254} + 8k : k \in [0,2^{251}-1]\}$.  If you use the keyspace defined here and multiply by the cofactor 8 then this gives the same thing, but that's not how X25519 is specified: clamping produces an element of $S$, and there is no explicit cofactor multiplication.  We should double-check the equivalence of these schemes.
- In 4.2: `One can implement the computation of the ephemeral key pair for Ed25519 using an existing Montgomery curve implementation by (1) generating a public-private key pair (k, R':=k*G') for Curve25519;(2) representing this public-private key as the pair (k, R:=k*G) for Ed25519.`  This is confusing, because $G$ and $G'$ are not the same point.  There's also this explicit-vs-implicit question for Curve25519 key pairs.  Finally, "*key pair* for Curve25519" makes me think of Curve25519 the protocol, rather than Curve25519 the curve, and in the protocol the public key is only an x-coordinate.

### 5 Caveats

- In 5.1: the u-coordinate-only compression of RFC7748 (X25519) is not "lossy" (the dropped v-coordinate was never part of the protocol or keys), unless "lossy" means that it maps the point at infinity and (0,0) to the same value, 0.
- In 5.3: "NOTE 1" is interesting, but also kind of pointless in this kind document.
- In 5.3: "NOTE 2" makes me wonder how all these isogenies were found/computed.  It might be worth noting that this 2-isogeny does not preserve the endomorphism ring: you move one level up to the "crater" of the 2-volcano with this isogeny.  On a more basic level, the curves don't have the same abelian group structure: the twist of Curve25519 has a cyclic group, while the 2-isogenous curve has non-cyclic 2-torsion.  This is not an issue with the 47-isogeny from Curve25519, which restricts to an isomorphism on groups of rational points.

### 6 Implementation considerations

Clarification: `All NIST curves [FIPS-186-4] and Brainpool curves [RFC5639] are Weierstrass curves with a=-3 domain parameter, thus facilitating more efficient elliptic curve group operations (via so-called Jacobian coordinates).` - this "more efficient" is w.r.t. general short Weierstrass curves with a != -3.

### 8 Security considerations

- `...which is either an isomorphism of a low-degree isogeny`: 47 isn't that low (well, not unless you're a CSIDH implementer)!
- `the complexity of cryptographic problems (such as the discrete logarithm problem) of curves related via a low-degree isogeny are tightly related.  Thus, the use of these techniques does not negatively impact cryptogaphic security of elliptic curve operations.`: this can be made more precise.  The 47-isogeny is an isomorphism on the level of groups of points (because 47 is coprime to the group order), and since the groups are isomorphic their DLPs have equivalent difficulty.  (The 2-isogeny from the twist restricts to an isomorphism of the prime-order subgroups, which is where all the DLP difficulty comes from in that case, so similarly the DLPs have equivalent difficulty.)
- `the use of these techniques does not negatively impact cryptogaphic security of elliptic curve operations`: this might be true in the sense of DLP operations, but the existence of an isomorphism doesn't mean that things like side-channel safety extends from a Curve25519 implementation to a Wei25519 implementation.  So maybe "security of elliptic curve operations" should be changed to something like "security of the underlying elliptic curve discrete logarithms"?

### 14 References

`[Wei-Ladder]` was published in PKC 2002, and there's no reason to cite a preprint instead here instead of the definitive version.  This reference can be updated to: Tetsuya Izu and Tsuyoshi Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant Against Side Channel Attacks", PKC 2002, Lecture Notes in Computer Science Vol. 2274, Springer-Verlag, 2002.

### Appendix B

I'm not really sure why this is separate from Appendix A.

- In B.1: The notation `(P)` for the subgroup generated by P is nonstandard and has a fair potential for confusion; `<P>` would be more typical.
- In B.1: `The order of curve E` should be "The order of *a* curve E"
- In B.1: `All curves of prime order are cyclic`: more generally, if the order is not divisible by a square > 1 then the group is cyclic.
- In B.1: `if h*P = O (and is a high-order point otherwise); this point has order n` is slightly ambiguous: `the point P has order n` would be a little clearer.
- In B.1: `Random points R of (P), where P has order l, ... computing R:=k*P, where R has rder l/gcd(k,l)`: this "where" sounds like a restriction on R, rather than a corollary.  Something like `computing R:=k*P. The point R has order l/gcd(k,l)` would be clearer.
- In B.1: `unless k is a multipl of n`: this `n` should be an `l`, but then `k` cannot be a multiple of `l` unless it is zero (because it was sampled from [0,l-1]).
- In B.1: `If P is a fixed base point G of the curve...`: P is never used again in this paragraph (or indeed, in the rest of this appendix), so its appearance here is confusing. Maybe this could be rephrased purely in terms of G?
- In B.1: `If this representation is nonzero, R has order n`: this is only true for `n` prime.
- In B.1: `...|E| relatively close to q, where, in fact, |E|=q+1-t`: this "where" is grammatically confusing.  `...|E| relatively close to q. In fact, |E|=q+1-t` would be clearer.
- In B.1: `Points that are both points of E and E'` should be "Points that are points of both E an E'", which sounds funny because of the "Points that are points"; maybe `Points that are simultaneously in E and in E'` would be better?
- In B.1: `Two curves E and E'... are said to be isomorphic if these have the same group structure`: **this is wrong**.  They are isomorphic if there exists an isomorphism *of elliptic curves*, not a group isomorphism.  For example, if q is fixed and large, and n is a prime in the Hasse interval close to q, then there are O(\sqrt{q}) non-isomorphic curves of order n, all with groups of points isomorphic to Z/nZ.  These curves are all isogenous, but they are generally connected by isogenies of extremely large degree, which cannot be computed efficiently - so the DLP in these curves is not necessarily equivalent, in the sense that the DLP in one curve cannot necessarily be mapped into another in polynomial time.  There is certainly no algebraic isomorphism between the curves; generally, mapping points homomorphically from one group into another means solving DLPs!  So even though the groups are isomorphic, I think it is wrong (and seriously misleading) to say that these curves are isomorphic.
- In B.2: `where g^0 is the identity element 1 of GF(q)`: 1 is the multiplicative identity element (0 is the additive identity element).  It might be clearer to just say "the multiplicative identity element 1 of GF(q)", or even simpler "the element 1 of GF(q)".
- In B.2: `the set GF(q)\{0} is cyclic`: this should be `the set GF(q)\{0}` forms a cyclic group (a set cannot be cyclic).
- In B.2: `computing square roots and inverses in GF(q) - if these exist`: inverses always exist (except for 0).  I think the "if these exist" qualifier belongs with the square roots instead.
- In B.2: `Readers not interested in this, could simply view...`: remove the comma.

### Appendix C

- In C.1: `For each point P of the Weierstrass curve W_{a,b}, the point at infinity O serves as identity element`: the identity element is always defined for the group, not w.r.t. each element P.  This would be clearer as `On the Weierstrass curve W_{a,b}, the point at infinity serves as identity element`.
- In C.1: `One has P + (-P) = O`: this is an example of somewhere where the notation `(P)` for the subgroup generated by P causes a bad ambiguity.
- In C.1: `...let Q:=P1 + P2, where Q is not the identity element.  Then Q:=(X, Y)`: Q is being defined in `Q:=P1 + P2`, so you can't restrict it in this way, and then the second definition `Q:=(X, Y)` is tautological.  Maybe this would be clearer as `...let Q:= P1 + P2.  If X1 = X2 and Y1 = -Y2, then Q is the identity element. Otherwise, Q = (X,Y), where...`
- In C.2: Exactly the same comments apply here as for C.1/short Weierstrass curves.
- In C.3: Same comments here as for C.1/short Weierstrass curves.

### Appendix D

- In D.1: `while mapping each other point (u,v) of M_{A,B} to the point (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}`: what about the two points of order two on M_{A,B} not equal to (0,0) (i.e., the points where v = 0 but u != 0)?  The image is not defined.  This situation may be covered/prohibited by the Note on twisted Edwards curves, but no such condition was imposed on the Montgomery curves here...
- In D.2: `Note that not all Weierstrass curves can be injectively mapped to Montgomery curves`: I don't think the "injectively" makes any sense here.  Some Weierstrass curves cannot be transformed into Montgomery form in any way.  Also note that having a point of order 2 is necessary *but not sufficient* for the existence of a Montgomery model.

### Appendix E

- In E.2: `as a shift of (p+A)/3 for the isomorphic mapping and -(p+A)/3 for its inverse, where delta=(p+A)/3 is...`: this should probably be `as a shift of delta for the isomorphic mapping and -delta for its inverse, where delta:=(p+A)/3 is...`

### Appendix H

- `Point decompression... where one tries and recover` should be `where one tries to recover`
- `from its compressed representation and information on the domain parameters of the curve`: 

### Appendix J

It would be good if the base points on the various curves were mapped onto each other by the isomorphisms/isogenies defined above; this is probably the case, but it should still be mentioned explicitly here. 

### Appendix K

- I'm really not convinced that this is necessary: it's long, it's repetitive, it's of marginal interest, and it doesn't fit with the code-reuse/mapping theme of the main document (except for the mapping into the twisted Edwards curve).  These maps are not operations of primary interest, so this appendix amounts to 11 highly technical pages worth of bloat. I really don't understand the motivation for including this in this document. 
- In K.2: It would be worth mentioning that the "Fermat" inversion 1/y = y^{q-2} in GF(q) works also for q = p prime, and that it is easier to implement in constant-time (where this is relevant/required).
- In K.4.1: `If t is an element of GF(q) that is not a square... yields an affine point P(t)... Let P0:=(X0,Y0) be a fixed affine point of W_{a,b} for which neither P0, P0 + P(t), not P0 - P(t) is in the small subgroup`: it should be made clear that this property is supposed to hold *for all nonsquare t*.
- In K.4.2: Same remark as above for K.4.1

### Appendix L

`This section illustrates how isogenies can be used to yield curves with specific properties (here, illustrated for the "BitCoin" curve secp256k1).`  What are these specific properties in this instance?  The new curve secp256k1.m is not in Montgomery form, does not have a = -3 or -1, does not have particularly nice coefficients...  We have to go back to NOTE 2 of Appendix K to find out that the objective here is just to map from secp256k1 to a Weierstrass curve with nonzero a and b coefficients.  This can only be achieved with an isogeny, not an isomorphism, but then why not transform into one of these more "useful" restricted-short-Weierstrass models (e.g. a = 1 or a = -3)?  That would be more coherent with the "code re-use" motivation of the document.  If all you want is nonzero coefficients then virtually any rational isogeny would do the job, and that reduces this entire appendix to an extra sentence in NOTE 2 of Appendix K.

### Appendix M

- In M.1: `with as base point the point (Gx, Gy)` should be `with base point (Gx, Gy)`.
- Same for the `with as base point the point (GX, GY)`.
- In M.2: Same "delta" comment as for E.2.

### Appendix N

What is the point of Edwards448? Is this just some intermediate curve?  Does this curve really need to be named and specified?

> On 12 Nov 2021, at 08:42, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
> 
> Thanks, we'll be looking forward to it.
> 
> Regards,
> Stanislav
> 
> On Fri, 12 Nov 2021 at 10:35, Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
> Sorry about this, am pushing my colleague and we’ll get it done.
> 
>> On 12 Nov 2021, at 07:35, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>> 
>> Hi Karthik,
>> 
>> >> We’ll send our review early next week.
>> The authors keep asking me about the review - could you please finish it today (it is already later than "early this week" :) )?..
>> 
>> Regards,
>> Stanislav
>> 
>> On Sat, 6 Nov 2021 at 01:55, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>> Thank you, Karthik!
>> 
>> Regards,
>> Stanislav 
>> 
>> On Sat, 6 Nov 2021 at 00:33, Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
>> Hi Stanislav,
>> 
>> My colleague and I dropped the ball on this, but have made progress this week.
>> We’ll send our review early next week.
>> 
>> -Karthik
>> 
>>> On 5 Nov 2021, at 19:27, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> (CC’ing the second Karthik’s address that I am aware of.)
>>> 
>>> Karthik, please let me know about the status of your review. The authors have already asked us about the status of their review today, so my question to you yesterday was reasonable. 
>>> 
>>> Regards, 
>>> Stanislav 
>>> 
>>> On Thu, 4 Nov 2021 at 20:50, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>> Dear Karthik,
>>> 
>>> I may be missing something here, but could you please remind me whether you had sent a review for that document?..
>>> 
>>> Regards,
>>> Stanislav 
>>> 
>>> On Wed, 11 Aug 2021 at 17:01, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>> In my opinion, it will be absolutely fine, taking the size of the document into account.
>>> 
>>> Thank you, Karthik!
>>> 
>>> Regards,
>>> Stanislav (on behalf of the CFRG Chairs)
>>> 
>>> On Wed, 11 Aug 2021 at 16:58, Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
>>> Is 1 month too long a wait?
>>> 
>>>> On 11 Aug 2021, at 09:52, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>>> 
>>>> Great, thanks!
>>>> 
>>>> How much time will you need for this (taking 146 pages into account) 
>>>> I would like to send a message to the authors (CC'ing crypto-panel mailing list).
>>>> 
>>>> Regards,
>>>> Stanislav
>>>> 
>>>> On Wed, 11 Aug 2021 at 16:43, Karthikeyan Bhargavan <[email-masked] <mailto:[email-masked]>> wrote:
>>>> Sure, I got a request on another thread a well and can do this (with help from some colleaugues.)
>>>> 
>>>> -K.
>>>> 
>>>>> On 11 Aug 2021, at 09:39, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>>>> 
>>>>> Karthik,
>>>>> 
>>>>> Can you do a review of this document (as a Crypto Review Panel member)?
>>>>> 
>>>>> Regards,
>>>>> Stanislav
>>>>> 
>>>>> On Fri, 6 Aug 2021 at 12:46, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>>>> Dear Karthik,
>>>>> 
>>>>> Nick, Alexey and I have had some discussion about reviewing the "Alternative Elliptic Curve Representations" draft, draft-ietf-lwig-curve-representations-21, https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/> - may we ask you to do the review (on behalf of the Crypto Panel)?
>>>>> 
>>>>> Regards,
>>>>> Stanislav
>>>>> 
>>>>> On Fri, 16 Jul 2021 at 11:50, Stanislav V. Smyshlyaev <[email-masked] <mailto:[email-masked]>> wrote:
>>>>> Dear Crypto Panel Experts, 
>>>>> 
>>>>> We've obtained a request for review of the version -21 of the "Alternative Elliptic Curve Representations" draft, draft-ietf-lwig-curve-representations-21, https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ <https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/>
>>>>> 
>>>>> The Crypto Panel (that was my review back then) provided a review of the -00 version three years ago:
>>>>> https://mailarchive.ietf.org/arch/msg/crypto-panel/1itH0lM9w0bZiADJXQkizr8JTiA/ <https://mailarchive.ietf.org/arch/msg/crypto-panel/1itH0lM9w0bZiADJXQkizr8JTiA/>
>>>>> 
>>>>> The document has changed significantly since then, so the authors ask for a new review. 
>>>>> 
>>>>> The chairs would like to ask the Crypto Panel to provide a review (another pair of eyes + reviewing all the changes in the document).
>>>>> 
>>>>> Any volunteers?
>>>>> 
>>>>> Regards,
>>>>> Stanislav (for CFRG Chairs)
>>>> 
>>> 
>> 
>

---

From: Erik Kline <[email-masked]>
Date: Mon, 15 Nov 2021 09:10:54 -0800

Karthikeyan,

Thank you so much for taking the time and giving such a detailed review!

Much appreciated,
-Erik

On Fri, Nov 12, 2021 at 5:28 AM Karthikeyan Bhargavan <
[email-masked]> wrote:

> I discussed this review with Ben and agree with his concerns and it would
> be great if the authors could address his questions.
>
> One way to do this would be to extend Implementation Considerations
> (and/or Implementation Status) with concrete examples of code reuse in
> Wei25519 implementations, quantified in lines of code, for example.
> If most of the code in these implementations is in the field arithmetic,
> which can be reused between representations anyway, the argument for this
> draft becomes less compelling.
>
> Best regards,
> Karthik
>
> ===
> [Curve representations draft](
> https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/)
>
> This draft specifies a series of new elliptic curves related to Curve25519
> and Curve448, and transformations between these new curves and
> Curve25519/Curve448.  The motivation is essentially code re-use: legacy
> elliptic-curve software and hardware works with the classic "short
> Weierstrass form", often with the a-coefficient set to -3, but in more
> recent protocols and software we might work with Curve25519 and Curve448 in
> either "Montgomery form" or "twisted Edwards form" (depending on the
> protocol), for efficiency reasons.  On the surface, these equation forms
> are not the same, so the newer curves are incompatible with legacy ECC code.
>
> This document bridges the gap by writing down isomorphisms to short
> Weierstrass curves with a=-3 where such isomorphisms exist, and isogenies
> (homomorphic maps) where isomorphisms do not exist.  It also specifies
> several other curves and maps, of various levels of usefulness.
>
> I am not entirely convinced by the code re-use argument here.  I agree
> that this is an interesting goal, given the time and effort it takes to
> develop and certify cryptographic software and especially hardware.  But
> for a concrete example, suppose we have an existing implementation
> elliptic-curve scalar multiplication on NIST P256, and we want to use this
> document to re-use that software for scalar multiplication on Curve25519:
>
> 1. The curve group operations for P256 can be and reused, and so can the
> scalar multiplication algorithm(s), insofar as they just call the curve
> group operations.
> 2. The underlying field arithmetic implementation must be
> rewritten/replaced, because these curves work modulo different primes.
> Generally this isn't just a matter of changing a hard-coded value for the
> prime p: the different primes have been chosen to allow completely
> different optimized modular reduction algorithms.
> 3. The code to actually map points between the two curves must be added,
> and in some cases this code will be particularly large.  In particular, the
> code here to convert from Curve25519 to Weierstrass with a=-3 involves 9kb
> worth of data to define the isogeny (to say nothing of the code to evaluate
> the isogeny).
> Comparing the small amount of code saved to the new code to be added, and
> the possible modifications to the protocol: is this really worth it?  If
> you're going to have to add a whole new field arithmetic implementation
> _and_ an extremely heavy isogeny-evaluation function (specified by a
> massive collection of precomputed coefficients), then maybe you would be
> better off just implementing Curve25519 properly.
>
> One might argue that the real benefit here would be for curve
> implementations in hardware, where changing (and re-certifying) designs is
> extremely slow, but I think that argument is defeated by the fact that the
> finite field arithmetic (the lowest level) still has to be rewritten.
>
> Ironically, herefore, this document could be read as a convincing argument
> **against** code re-use.  Of course, I might just be totally missing the
> point. In that case, since I have read all 150 pages and still missed the
> point, I think this means that the author hasn't fully explained the point.
>
> The document is _extremely_ long, and often quite repetitive.  There is
> too much repetition of boilerplate text blocks for the various
> transformations applied to different concrete instances.  To give just one
> example: Appendix M is essentially the same as Appendix E, but with
> different curve parameters.  There must be a way to minimise this
> repetition (especially given the focus on code re-use!).
>
> - Appendix L can also be removed: it is a long and unneccessary
> elaboration on a remark in Appendix K, and therefore out of scope.
> - Appendix N seems mostly superfluous: I don't understand why this
> Edwards448 curve needs to be defined and named (we already have Ed448...)
>
> Most of the technical content is uncontroversial, and it is mostly correct
> (detailed technical comments follow).  I am not competent to evaluate
> Sections 10, 11, and 12, but I have checked the rest in detail.
>
> One key technical point: as mentioned above, the transfer between many of
> the curves here requires an isogeny (a homomorphic map) rather than an
> isomorphism (essentially a change of coordinates).  One of the most
> important isogenies here - the one from Curve25519 to Wei25519.-3 - has
> degree 47.  This means that specifying it involves, at a minimum, a
> degree-23 polynomial w(x).  This polynomial w(x) is dense, so we need to
> specify (and store) 23x 32-byte coefficients.  This obviously requires a
> lot of space!  I say "at a minimum", because two more polynomials, u(x) and
> v(x), of similar degree, are required. Mathematically they can be derived
> from w(x), but for algorithmic simplicity it may be more convenient to
> specify them in their expanded form, as is done here.  Then, the "dual" map
> from Wei25519.-3 back to Curve25519 has its own large u, v, and w.
> Ultimately, this means a *lot* of space: 9kB of memory in code, and 12+
> pages of this document.
>
> Reducing this size (and evaluation time) is important if this is to be
> made practical.  I have checked, and I agree with the author that there is
> no isogeny of *prime* degree less than 47 from Curve25519 to a
> short-Weierstrass curve with a=-3.  However, there *is* such an isogeny of
> composite degree 46 (I could not find any lower-degree composite isogenies
> that do the job).  This doesn't look like much of an improvement on the
> surface, but the degree-46 isogeny is the composite of a degree-2 isogeny
> (very easy to specify/compute) and a degree-23 isogeny (roughly half the
> coefficients and complexity compared with the 47-isogeny).  This means that
> by changing the definition of Wei25519.-3 to be the codomain of the
> 46-isogeny instead of the 47-isogeny, the time and space required to encode
> and compute the isogeny will be literally cut in half.  Of course, half of
> 9kB is still quite expensive, and it remains to be seen if anyone will
> consider this practical for applications, but I think it is still an
> improvement that the author might want to consider using.
>
> ## Technical remarks
>
> - most instances of "hereof" should be "thereof", though something less
> archaic than "(t)hereof" would be even better
>
> - In 4.1: `Moreover, with X25519, private keys are generated in the
> interval [2^251,2^252-1] rather than in the interval [1,n-1] (the so-called
> "clamping") and one uses as base point G':=h*G, where G, n, and h are,
> respectively, the fixed base point, the order of the base point, and the
> co-factor of the curve in question`: I think this is wrong.  The private
> keyspace for X25519 is $S = \{2^{254} + 8k : k \in [0,2^{251}-1]\}$.  If
> you use the keyspace defined here and multiply by the cofactor 8 then this
> gives the same thing, but that's not how X25519 is specified: clamping
> produces an element of $S$, and there is no explicit cofactor
> multiplication.  We should double-check the equivalence of these schemes.
> - In 4.2: `One can implement the computation of the ephemeral key pair for
> Ed25519 using an existing Montgomery curve implementation by (1) generating
> a public-private key pair (k, R':=k*G') for Curve25519;(2) representing
> this public-private key as the pair (k, R:=k*G) for Ed25519.`  This is
> confusing, because $G$ and $G'$ are not the same point.  There's also this
> explicit-vs-implicit question for Curve25519 key pairs.  Finally, "*key
> pair* for Curve25519" makes me think of Curve25519 the protocol, rather
> than Curve25519 the curve, and in the protocol the public key is only an
> x-coordinate.
>
> ### 5 Caveats
>
> - In 5.1: the u-coordinate-only compression of RFC7748 (X25519) is not
> "lossy" (the dropped v-coordinate was never part of the protocol or keys),
> unless "lossy" means that it maps the point at infinity and (0,0) to the
> same value, 0.
> - In 5.3: "NOTE 2" makes me wonder how all these isogenies were
> found/computed.  It might be worth noting that this 2-isogeny does not
> preserve the endomorphism ring: you move one level up to the "crater" of
> the 2-volcano with this isogeny.  On a more basic level, the curves don't
> have the same abelian group structure: the twist of Curve25519 has a cyclic
> group, while the 2-isogenous curve has non-cyclic 2-torsion.  This is not
> an issue with the 47-isogeny from Curve25519, which restricts to an
> isomorphism on groups of rational points.
>
> Clarification: `All NIST curves [FIPS-186-4] and Brainpool curves
> [RFC5639] are Weierstrass curves with a=-3 domain parameter, thus
> facilitating more efficient elliptic curve group operations (via so-called
> Jacobian coordinates).` - this "more efficient" is w.r.t. general short
> Weierstrass curves with a != -3.
>
> - `...which is either an isomorphism of a low-degree isogeny`: 47 isn't
> that low (well, not unless you're a CSIDH implementer)!
> - `the complexity of cryptographic problems (such as the discrete
> logarithm problem) of curves related via a low-degree isogeny are tightly
> related.  Thus, the use of these techniques does not negatively impact
> cryptogaphic security of elliptic curve operations.`: this can be made more
> precise.  The 47-isogeny is an isomorphism on the level of groups of points
> (because 47 is coprime to the group order), and since the groups are
> isomorphic their DLPs have equivalent difficulty.  (The 2-isogeny from the
> twist restricts to an isomorphism of the prime-order subgroups, which is
> where all the DLP difficulty comes from in that case, so similarly the DLPs
> have equivalent difficulty.)
> - `the use of these techniques does not negatively impact cryptogaphic
> security of elliptic curve operations`: this might be true in the sense of
> DLP operations, but the existence of an isomorphism doesn't mean that
> things like side-channel safety extends from a Curve25519 implementation to
> a Wei25519 implementation.  So maybe "security of elliptic curve
> operations" should be changed to something like "security of the underlying
> elliptic curve discrete logarithms"?
>
> ### 14 References
>
> `[Wei-Ladder]` was published in PKC 2002, and there's no reason to cite a
> preprint instead here instead of the definitive version.  This reference
> can be updated to: Tetsuya Izu and Tsuyoshi Takagi, "A Fast Parallel
> Elliptic Curve Multiplication Resistant Against Side Channel Attacks", PKC
> 2002, Lecture Notes in Computer Science Vol. 2274, Springer-Verlag, 2002.
>
> ### Appendix B
>
> - In B.1: The notation `(P)` for the subgroup generated by P is
> nonstandard and has a fair potential for confusion; `<P>` would be more
> typical.
> - In B.1: `All curves of prime order are cyclic`: more generally, if the
> order is not divisible by a square > 1 then the group is cyclic.
> - In B.1: `if h*P = O (and is a high-order point otherwise); this point
> has order n` is slightly ambiguous: `the point P has order n` would be a
> little clearer.
> - In B.1: `Random points R of (P), where P has order l, ... computing
> R:=k*P, where R has rder l/gcd(k,l)`: this "where" sounds like a
> restriction on R, rather than a corollary.  Something like `computing
> R:=k*P. The point R has order l/gcd(k,l)` would be clearer.
> - In B.1: `unless k is a multipl of n`: this `n` should be an `l`, but
> then `k` cannot be a multiple of `l` unless it is zero (because it was
> sampled from [0,l-1]).
> - In B.1: `If P is a fixed base point G of the curve...`: P is never used
> again in this paragraph (or indeed, in the rest of this appendix), so its
> appearance here is confusing. Maybe this could be rephrased purely in terms
> of G?
> - In B.1: `...|E| relatively close to q, where, in fact, |E|=q+1-t`: this
> "where" is grammatically confusing.  `...|E| relatively close to q. In
> fact, |E|=q+1-t` would be clearer.
> - In B.1: `Points that are both points of E and E'` should be "Points that
> are points of both E an E'", which sounds funny because of the "Points that
> are points"; maybe `Points that are simultaneously in E and in E'` would be
> better?
> - In B.1: `Two curves E and E'... are said to be isomorphic if these have
> the same group structure`: **this is wrong**.  They are isomorphic if there
> exists an isomorphism *of elliptic curves*, not a group isomorphism.  For
> example, if q is fixed and large, and n is a prime in the Hasse interval
> close to q, then there are O(\sqrt{q}) non-isomorphic curves of order n,
> all with groups of points isomorphic to Z/nZ.  These curves are all
> isogenous, but they are generally connected by isogenies of extremely large
> degree, which cannot be computed efficiently - so the DLP in these curves
> is not necessarily equivalent, in the sense that the DLP in one curve
> cannot necessarily be mapped into another in polynomial time.  There is
> certainly no algebraic isomorphism between the curves; generally, mapping
> points homomorphically from one group into another means solving DLPs!  So
> even though the groups are isomorphic, I think it is wrong (and seriously
> misleading) to say that these curves are isomorphic.
> - In B.2: `where g^0 is the identity element 1 of GF(q)`: 1 is the
> multiplicative identity element (0 is the additive identity element).  It
> might be clearer to just say "the multiplicative identity element 1 of
> GF(q)", or even simpler "the element 1 of GF(q)".
> - In B.2: `the set GF(q)\{0} is cyclic`: this should be `the set
> GF(q)\{0}` forms a cyclic group (a set cannot be cyclic).
> - In B.2: `computing square roots and inverses in GF(q) - if these exist`:
> inverses always exist (except for 0).  I think the "if these exist"
> qualifier belongs with the square roots instead.
> - In C.1: `For each point P of the Weierstrass curve W_{a,b}, the point at
> infinity O serves as identity element`: the identity element is always
> defined for the group, not w.r.t. each element P.  This would be clearer as
> `On the Weierstrass curve W_{a,b}, the point at infinity serves as identity
> element`.
> - In C.1: `One has P + (-P) = O`: this is an example of somewhere where
> the notation `(P)` for the subgroup generated by P causes a bad ambiguity.
> - In C.1: `...let Q:=P1 + P2, where Q is not the identity element.  Then
> Q:=(X, Y)`: Q is being defined in `Q:=P1 + P2`, so you can't restrict it in
> this way, and then the second definition `Q:=(X, Y)` is tautological.
> Maybe this would be clearer as `...let Q:= P1 + P2.  If X1 = X2 and Y1 =
> -Y2, then Q is the identity element. Otherwise, Q = (X,Y), where...`
> - In D.1: `while mapping each other point (u,v) of M_{A,B} to the point
> (x,y):=(u/v,(u-1)/(u+1)) of E_{a,d}`: what about the two points of order
> two on M_{A,B} not equal to (0,0) (i.e., the points where v = 0 but u !=
> 0)?  The image is not defined.  This situation may be covered/prohibited by
> the Note on twisted Edwards curves, but no such condition was imposed on
> the Montgomery curves here...
> - In D.2: `Note that not all Weierstrass curves can be injectively mapped
> to Montgomery curves`: I don't think the "injectively" makes any sense
> here.  Some Weierstrass curves cannot be transformed into Montgomery form
> in any way.  Also note that having a point of order 2 is necessary *but not
> sufficient* for the existence of a Montgomery model.
>
> ### Appendix E
>
> - In E.2: `as a shift of (p+A)/3 for the isomorphic mapping and -(p+A)/3
> for its inverse, where delta=(p+A)/3 is...`: this should probably be `as a
> shift of delta for the isomorphic mapping and -delta for its inverse, where
> delta:=(p+A)/3 is...`
>
> ### Appendix H
>
> It would be good if the base points on the various curves were mapped onto
> each other by the isomorphisms/isogenies defined above; this is probably
> the case, but it should still be mentioned explicitly here.
>
> ### Appendix K
>
> - I'm really not convinced that this is necessary: it's long, it's
> repetitive, it's of marginal interest, and it doesn't fit with the
> code-reuse/mapping theme of the main document (except for the mapping into
> the twisted Edwards curve).  These maps are not operations of primary
> interest, so this appendix amounts to 11 highly technical pages worth of
> bloat. I really don't understand the motivation for including this in this
> document.
> - In K.2: It would be worth mentioning that the "Fermat" inversion 1/y =
> y^{q-2} in GF(q) works also for q = p prime, and that it is easier to
> implement in constant-time (where this is relevant/required).
> - In K.4.1: `If t is an element of GF(q) that is not a square... yields an
> affine point P(t)... Let P0:=(X0,Y0) be a fixed affine point of W_{a,b} for
> which neither P0, P0 + P(t), not P0 - P(t) is in the small subgroup`: it
> should be made clear that this property is supposed to hold *for all
> nonsquare t*.
> `This section illustrates how isogenies can be used to yield curves with
> specific properties (here, illustrated for the "BitCoin" curve secp256k1).`
>  What are these specific properties in this instance?  The new curve
> secp256k1.m is not in Montgomery form, does not have a = -3 or -1, does not
> have particularly nice coefficients...  We have to go back to NOTE 2 of
> Appendix K to find out that the objective here is just to map from
> secp256k1 to a Weierstrass curve with nonzero a and b coefficients.  This
> can only be achieved with an isogeny, not an isomorphism, but then why not
> transform into one of these more "useful" restricted-short-Weierstrass
> models (e.g. a = 1 or a = -3)?  That would be more coherent with the "code
> re-use" motivation of the document.  If all you want is nonzero
> coefficients then virtually any rational isogeny would do the job, and that
> reduces this entire appendix to an extra sentence in NOTE 2 of Appendix K.
>
> ### Appendix M
>
> What is the point of Edwards448? Is this just some intermediate curve?
> Does this curve really need to be named and specified?
>
>
> On 12 Nov 2021, at 08:42, Stanislav V. Smyshlyaev <[email-masked]>
> wrote:
>
> On Fri, 12 Nov 2021 at 10:35, Karthikeyan Bhargavan <
> [email-masked]> wrote:
>
>> On 12 Nov 2021, at 07:35, Stanislav V. Smyshlyaev <[email-masked]>
>> wrote:
>>
>> Hi Karthik,
>>
>> The authors keep asking me about the review - could you please finish it
>> today (it is already later than "early this week" :) )?..
>>
>> Regards,
>> Stanislav
>>
>> On Sat, 6 Nov 2021 at 01:55, Stanislav V. Smyshlyaev <[email-masked]>
>> wrote:
>>
>>> Thank you, Karthik!
>>>
>>> Regards,
>>> Stanislav
>>>
>>> On Sat, 6 Nov 2021 at 00:33, Karthikeyan Bhargavan <
>>> [email-masked]> wrote:
>>>
>>>> Hi Stanislav,
>>>>
>>>> On 5 Nov 2021, at 19:27, Stanislav V. Smyshlyaev <[email-masked]>
>>>> wrote:
>>>>
>>>> Karthik, please let me know about the status of your review. The
>>>> authors have already asked us about the status of their review today, so my
>>>> question to you yesterday was reasonable.
>>>>
>>>> Regards,
>>>> Stanislav
>>>>
>>>> On Thu, 4 Nov 2021 at 20:50, Stanislav V. Smyshlyaev <[email-masked]>
>>>> wrote:
>>>>
>>>>> Dear Karthik,
>>>>>
>>>>> I may be missing something here, but could you please remind me
>>>>> whether you had sent a review for that document?..
>>>>>
>>>>> Regards,
>>>>> Stanislav
>>>>>
>>>>> On Wed, 11 Aug 2021 at 17:01, Stanislav V. Smyshlyaev <
>>>>> [email-masked]> wrote:
>>>>>
>>>>>> On Wed, 11 Aug 2021 at 16:58, Karthikeyan Bhargavan <
>>>>>> [email-masked]> wrote:
>>>>>>
>>>>>>> On 11 Aug 2021, at 09:52, Stanislav V. Smyshlyaev <[email-masked]>
>>>>>>> wrote:
>>>>>>>
>>>>>>> Great, thanks!
>>>>>>>
>>>>>>> On Wed, 11 Aug 2021 at 16:43, Karthikeyan Bhargavan <
>>>>>>> [email-masked]> wrote:
>>>>>>>
>>>>>>>> On 11 Aug 2021, at 09:39, Stanislav V. Smyshlyaev <
>>>>>>>> [email-masked]> wrote:
>>>>>>>>
>>>>>>>> Karthik,
>>>>>>>>
>>>>>>>> On Fri, 6 Aug 2021 at 12:46, Stanislav V. Smyshlyaev <
>>>>>>>> [email-masked]> wrote:
>>>>>>>>
>>>>>>>>> Dear Karthik,
>>>>>>>>>
>>>>>>>>> Nick, Alexey and I have had some discussion about reviewing the
>>>>>>>>> "Alternative Elliptic Curve Representations" draft,
>>>>>>>>> draft-ietf-lwig-curve-representations-21,
>>>>>>>>> https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/ -
>>>>>>>>> may we ask you to do the review (on behalf of the Crypto Panel)?
>>>>>>>>>
>>>>>>>>> Regards,
>>>>>>>>> Stanislav
>>>>>>>>>
>>>>>>>>> On Fri, 16 Jul 2021 at 11:50, Stanislav V. Smyshlyaev <
>>>>>>>>> [email-masked]> wrote:
>>>>>>>>>
>>>>>>>>>> We've obtained a request for review of the version -21 of the
>>>>>>>>>> "Alternative Elliptic Curve Representations" draft,
>>>>>>>>>> draft-ietf-lwig-curve-representations-21,
>>>>>>>>>> https://datatracker.ietf.org/doc/draft-ietf-lwig-curve-representations/
>>>>>>>>>>
>>>>>>>>>> https://mailarchive.ietf.org/arch/msg/crypto-panel/1itH0lM9w0bZiADJXQkizr8JTiA/
>>>>>>>>>>
>>>>>>>>>> The chairs would like to ask the Crypto Panel to provide a review
>>>>>>>>>> (another pair of eyes + reviewing all the changes in the document).
>>>>>>>>>>
>>>>>>>>>> Any volunteers?
>>>>>>>>>>
>>>>>>>>>> Regards,