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

[Rene Struik <[e-mail]>]

Response to review comments on draft-ietf-lwig-curve-representations-21 
by Rene Struik (Jan 21, 2022)
status review: "crypto review panel" review
review request date: July 16, 2021 (by Erik Kline)
review completion date: November 12, 2021 (communicated by Karthik 
Bhargavan; actual reviewer: Ben Smith)

Note: focus with responses to the crypto review panel review is on 
cryptographic matters. Responses bracketed by RS>> and <<RS

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

[Curve representations 
draft](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.

RS>>
Main motivation for draft is two-fold: (a) reuse of existing 
implementations; (b) reuse of existing specifications. Side motivation: 
background material useful for implementors or for cross-referencing 
with future specification work.
<<RS

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.

RS>>
The above analysis seems to assume that implementors primarily aim for 
speed, which is not always the case, since it would preclude algorithm 
and domain parameter agility, and hamper reuse of certified modules with 
side-channel measures. Please see Section 6 (Implementation 
Considerations), which already delves into this topic and discusses 
trade-offs between reusing existing generic short-Weierstrass curve 
implementations (e.g., a hardware-assisted implementation of the 
Brainpool curve BP-256 without hardcoded domain parameters) and 
optimizing an implementation for a particular new curve and domain 
parameters from scratch. See also Section 7 (Implementation Status), 
which gives some examples with, e.g., NXP chipsets and (in rev23) with 
code by ANSSI (the French information security agency).
<<RS

RS>>
The draft requests code points for Wei25519 and Wei448 and *not* for the 
curves Wei25519.-3 and Wei448.-3. Those were discussed in the draft to 
assist practitioners who may have hardcoded a=-3 parameters in their 
implementations, where using isogenies provides a mechanism to whip 
parameters into the proper shape, so that interfaces to a scalar 
multiplier could be made to work. Should one wish to use isogenies, the 
protocol tweak (#4 above) is minor (instead of public-key pair (k,k*G) 
one gets (l*k, l*k*G), where l is the degree of the applicable isogeny), 
as discussed in the second para of Section 3 (Use of Representation 
Switches).
<<RS

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!).

RS>>
I would be happy to consider suggestions to streamline text, as long as 
this does not jeopardize clarity and readability by non-domain experts 
(the target audience of this draft), since - at present - do not see how 
this can be easily done. Please bear in mind that this draft is aimed at 
humans and not machines, so I opted against a bunch of dense, but 
unreadable routines.
<<RS

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...)

RS>>
I don't think any of these sections can be easily removed, without 
jeopardizing the goal of describing in a succinct way to practitioners 
how alternative representations could help them with implementations. As 
to Appendix I, I am not aware of any existing text that discusses data 
conversions, including bit- and byte-orderings, in a precise, complete, 
and error-free way, so decided to set the record straight; as to 
Appendix Q, this was including due to continuing misconceptions on the 
correct definition of ECDSA by some developers and imprecise 
specifications of ECDSA in, e.g., RFC 8152, when the bit-size of the 
curve group is not byte-size (see also first para of that appendix); As 
to Appendix P, again, I am not aware of any existing text that describes 
this; Appendix K provides essential routines for taking square roots and 
inverses, including some speed-ups, and provides a mechanism for 
alternative representations of random curve points as random bit strings 
(based on Mehdi Tibouchi's papers) (see also Section 9 (Privacy 
Considerations), where future work can easily standardize this via 
cross-referencing). Please bear in mind that most of this material has 
been in the draft since early July 2019 (yes - IETF is very slow). As to 
Appendix N, the curve Edwards448 is used with EdDSA (RFC 8032), so a 
relevant alternative representation of Curve448 for practitioners and IETF.
<<RS

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.

RS>>
Please see my earlier remark, where I indicated that I only requested 
for codepoints for the curves Wei25519 and Wei448. So, nothing precludes 
an implementor to use their favorite representation under the hood, 
whether this is a Montgomery curve, a twisted Edwards curve, 
short-Weierstrass curve with a=-3 via the isogeny in the draft or 
role-your-own isogenies, etc. I opted against adding text on composition 
of isogenies, since the draft is targeted at practitioners who are not 
necessarily domain experts, and might loose them. Besides, adding this 
altenative would not change the main messages.
<<RS

## 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.

RS>>
Section 4.1 specifies co-factor ECDH, as in all standards using 
short-Weierstrass curves, and illustrates how this works with Montgomery 
curves (in Note 1), first with all mandatory checks in standards 
(X25519+), and then as X25519 does this (with RFC7748). To check that 
this was correctly specified, simply observe that, with X25519, one 
exchanges keys X:=(h*x)*G=x*(h*G) and Y:=(h*y)*G=y*(h*G) and computes 
shared key K:=(h*x)*Y=h*x*y*(h*G) and take G':=h*G. The remaining text 
simply stipulates the relaxed checks on received values and relaxed way 
of generating a private key in a "half space".
<<RS

- 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.

RS>>
I do not understand this comment. Please note that G' and G are the base 
points of Curve25519 and Ed25519, respectively, where Step (2) uses the 
isomorphic mapping from Curve25519 to Ed25519 defined in Appendix E. 
Please note that (k, R':=k*G') is a random public-private key pair (see 
Appendix B.1, 4th and 5th para, and 1000s of papers that define this), 
i.e., k is a random integer in the interval [1,n-1]. Curve25519 is a 
specific Montgomery curve (both in this draft and in RFC7748), where the 
DH-flavor protocol in RFC7748 is called X25519 (and also described in 
Note 1 of Section 4.1).
<<RS

### 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.

RS>>
I am reluctant to add any esoteric (to non-domain experts) language on 
endomorphism rings, vulcanous, torsions, and rational points, since this 
would almost surely loose the target audience of practitioners of this 
draft. Notes 1 and 2 simply illustrate that, with slightly different 
domain parameter generation methods, one could have provided a better 
fit with existing implementations, with zero cost in practice. As such, 
this illustrates that - were one to produce another set of domain 
parameters in the future - one should perhaps take into account existing 
implementations better. Without these notes, the audience might have 
gotten the (incorrect) impression that this would not be possible. The 
u-coordinate only compression is indeed lossy, since without knowledge 
of the v-coordinate, e.g., the generation method of Ed25519 keys with 
Curve25519 implementations as a subroutine (as the example of Section 
4.2 does) is underspecified.
<<RS

### 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"?

RS>>
The computational cost of evaluating the isogenies in the draft is 
relatively negligible (roughly 3*l field multiplies with Horner scheme). 
With l=47, this yields relative incremental cost less than one multiply 
per scalar bit. Whether the term "low-degree" is that low is in the eye 
of the beholder, but allows easy statement on DLP complexity, without 
having to use technical lingo or "variable-itis" in this section 
(remember that, in Appendix B.1, the order h*n of the curve is such that 
co-factor h is relatively low and n is prime).
<<RS

### 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.

RS>>
The CACR reference in the draft is an update ("postprint"?) of the PKC 
2002 paper, but either reference does of course work.
<<RS

### 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]).

RS>>
I can add the bracketed text in "In particular, if P is a high-order 
point (of curve E of order h*n)" to remind the reader that concepts 
introduced before (including h and n prime) are still in scope.
<<RS

- 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.

RS>>
As to the definition of "isomorphism", there is a trade-off between 
precision and risk of loosing an audience (hence, the "in this document" 
preamble to the 6th paragraph). I don't think the precise definition of 
isomorphism matters *for this draft* (since has no impact on any other 
150- pages of the document). Nevertheless, what I change this as follows:
"Two curves E1 and E2 defined over the field GF(q) are said to be 
isogenous if these have the same order and are said to be isomorphic if 
the defining equation of E1 can be transformed into the defining 
equation of E2 via a so-called admissible change of variables. Note that 
isomorphic curves have necessarily the same order and are, thus, a 
special case of isogenous curves. Isomorphic curves have the same group 
structure, whereas this is not necessarily the case for isogenous 
curves. Further details are out of scope."?
Any suggestion that does not introduce too esoteric language welcome.
<<RS

- 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.

RS>>
With the draft, any construction involving twisted Edwards curve is 
supposed to be subject to the Note of Appendix C.3 (a square in GF(q), d 
not). To remove any unclarity, I will add
"Note that this is well-defined, since neither (A-2)/B nor A^2-4 are 
squares in GF(q), so M_{A,B} has a single point of order two and no 
affine points (u,v) with u=-1." and "Note that this is well-defined, 
since for points (x,y) of E_{a,d}, x=0 only if y=(+/-)1." to the mapping 
and inverse mapping, respectively.
<<RS

### 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.

RS>>
This is indeed the case. The domain parameters and relationships between 
base points between various curve models are all specified in Section 
E.2 and G.2. Same with Curve448 and family members.
<<RS

### 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.

RS>>
For secp256k1, the concrete instantation of the isogeny used with the 
constructions in Appendix K is essential: without this, one only obtains 
abstract function families, with a nondescript isogeny as parameter. 
This draft is targeted at practitioners who (should) care about details 
of practical choices.
<<RS

### 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?

RS>>
See previous remark: Edwards448 is used with EdDSA (RFC 8032), so of 
practical interest.
<<RS

On 2021-11-12 8:28 a.m., Karthikeyan Bhargavan wrote:
>
> 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.
>
RS>>

Simple question: how does one instantiate ECDSA with SHA-256 and 
Wei25519, where this could use Curve25519 under the hood, without 
actually doing the work? I do not understand how lines of code would be 
relevant as a metric here (some of this is dealt with in Section 6 
(Implementation Considerations) and Section 7 (Implementation Status), 
of the draft, though.

<<RS

> Best regards,
> Karthik
>
> [snip]
>
>
>> On 12 Nov 2021, at 08:42, Stanislav V. Smyshlyaev <[e-mail]> 
>> wrote:
>>
>> Thanks, we'll be looking forward to it.
>>
>> Regards,
>> Stanislav
>>
>> On Fri, 12 Nov 2021 at 10:35, Karthikeyan Bhargavan 
>> <[e-mail]> wrote:
>>
>>     Sorry about this, am pushing my colleague and we’ll get it done.
>>
>>>     On 12 Nov 2021, at 07:35, Stanislav V. Smyshlyaev
>>>     <[e-mail]> 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
>>>     <[e-mail]> wrote:
>>>
>>>         Thank you, Karthik!
>>>
>>>         Regards,
>>>         Stanislav
>>>
>>>         On Sat, 6 Nov 2021 at 00:33, Karthikeyan Bhargavan
>>>         <[e-mail]> 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
>>>>             <[e-mail]> 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
>>>>             <[e-mail]> 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 <[e-mail]> 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 <[e-mail]> wrote:
>>>>
>>>>                         Is 1 month too long a wait?
>>>>
>>>>>                         On 11 Aug 2021, at 09:52, Stanislav V.
>>>>>                         Smyshlyaev <[e-mail]> 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 <[e-mail]> 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 <[e-mail]> 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
>>>>>>                             <[e-mail]> 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
>>>>>>                                 <[e-mail]> 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/
>>>>>>
>>>>>>
>>>>>>                                     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/
>>>>>>
>>>>>>                                     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)
>>>>>>
>>>>>
>>>>
>>>
>>
>
>

-- 
email:[e-mail]  | Skype: rstruik
cell: [phone] | US: [phone]