[CFRG] Asking the advice on the draft of pairing-friendly curves

[Yumi Sakemi <[e-mail]>]

Dear CFRG members

We have asked CFRG chairs about our response to Rene's comments and
received their advice.
Following their advice, we would like to explain again the purpose of
our standardization of pairing-friendly curves, the selection process,
and how to respond to Rene's comments in RGLC.
After that, we would like to ask the advice of the CFRG members.

For more information about Rene's comments, please refer to the following URL
https://mailarchive.ietf.org/arch/msg/cfrg/pW71h3yUETnqedHsH0m3rwzPnm4/

First, the purpose and stance of our activities.
Our purpose is to standardize the secure parameters of pairing-friendly curves.
Due to the attack by Kim in CRYPTO 2016, the BN254 curve which is
widely used is no longer secure enough.
>From the viewpoints of the future internet, the number of
cryptographic applications using pairing is increasing in recent
years, and the types of curves, parameters, and security are varied.
Some of these still have weak parameters in their implementations, so
we strongly believe that it is pressing to standardize the secure
pairing-friendly curves.

For more information, from the standpoint of the authors of this
draft, we would like to remind our viewpoints based on our draft as a
following.

- We believe that it is important to have a standardized specification
that can refer to secure parameters of pairing-friendly curves.
- Since the IETF and IRTF focus on implementation, we would like to
know if it is implemented/used in the real world.
- For detailed calculation methods and data conversion methods, refer
to appropriate standardization documents without mentioning them, in
order to increase readability without making the draft unnecessarily
long.
- To avoid the risk of violating patents and losing the range of
accelerating methods freely chosen by implementers by including
detailed calculation methods.
Note: There is no patent on the parameters of the pairing-friendly
curves, but we are well aware that there is a patent on the
calculation method for acceleration.
- The position of this draft is not educational, but rather that the
detailed calculation methods can be useful to implementers with
appropriate citations.

In addition, we received a lot of comments from Rene, which were very
detailed we are very grateful for the comments from Rene, as they were
very valuable in terms of improving the quality of the technical
documentation of our draft.
The comments were carefully discussed among the authors, and the
comments were reflected as appropriate.
However, if a comment is not in line with our writing policy, we will
indicate the reason on GitHub.
For more information on responding to comments, please refer to the
following URL
https://github.com/cfrg/draft-irtf-cfrg-pairing-friendly-curves/issues

Also, this draft has passed the Expert Review.
In the Expert Review, we were advised to add some technical
descriptions, and we reflected them.
We believe that the quality of the document from a technical point of
view can be guaranteed for the RFC.

In addition, it was pointed out that the selection process of the
parameters may have been biased by a certain organization.
However, you can see from the following discussion with CFRG members
that we have an appropriate process regarding selection of parameters
and that we accept comments widely.

(1) Armando's email: agree with BN462
https://mailarchive.ietf.org/arch/msg/cfrg/sIzv6XLNuL8VHor5voO1ybO__oI/

(2) Chloe's email: comments for the CP curve and agree with our
recommended curves
https://mailarchive.ietf.org/arch/msg/cfrg/eAn3_8XpcG4R2VFhDtE_pomPo2Q/

(3-1) Scott's email: about another curve.
Comments on expanding polynomials and elliptic coefficients
https://mailarchive.ietf.org/arch/msg/cfrg/AWyX-JqAMZRaSiQvZbXezO83QZI/

(3-2) A reply from Kenny Paterson, the chair at the time, about the
selection of the curve to post.
https://mailarchive.ietf.org/arch/msg/cfrg/19XqFwzdUXcn0CgsaShNbqrc1zs/

(3-3) Agreed with BLS12-381 from Scott.
https://mailarchive.ietf.org/arch/msg/cfrg/WHLTC50jx7CzS9H0kZp6Fae6tJs/

(4) Asking for BLS24 from Scott'
https://mailarchive.ietf.org/arch/msg/cfrg/0Ms6CmcOlsnZ1WyBjbLdoh8t8jc/

Secondly, Rene claims that not all comment responses have been
answered. We are addressing each and every his comment and responding
to all of them.
In fact, we have responded to every comment, and for the ones that
have not been reflected in the draft, we have included the reason on
GitHub, but since it was pointed out that it is difficult to check on
GitHub, we will attach it at the end of this email, even though it is
long.

As shown above, we have reviewed our stance and activities for
standardization regarding the current parameters of pairing-friendly
curves and presented our response to Rene's comments.
We would like to receive your advice on our activities from the CFRG
ML members to order to progress 2nd RGLC as a next step.

Best regards,
Yumi

P.S.
Followings are our reply comments for Rene's comments in RGLC.
---
(Detaild Comments)

> Section 1.2 (and also elsewhere) seems to conflate standardization of parameters,
> availability of libraries, and actual deployment, where there is an unusual prominence > (for an IRTF document) of company names. Wouldn't it make more sense to describe potential
> applications of pairing based cryptography in more technical terms, e.g., in terms of
> facilitating aggregate signatures, remote attestation, etc., and provide a brief
> description (and a technical reference)?

Thank you for your comment!
We think no problem that there is no special intention to promote the
company names in the draft, and they are shown to indicate the actual
adaptive status of the pairing-friendly curves.
If need, we expect that it will be pointed out again in the future
standardization process (e.g., IRSG Reviews), so we would like to
discuss how to update it with the reviewer at that time.


> Section 1.3: the main point of the extTNFS attack is that it tries and solve the DLP in
> low-degree extension field GF(p^t) for small composite t>1 faster. To bring this point
> accross, I suggest changing reference to "by the attack" (l. 5 of Section 1.3) by
> something more closely reflecting this.

Thank you for your suggestion!
We agreed with your comments and added an explanation of the attack.


> Section 2.3, 4th para (top of p. 8): elaborate on the "BN curves always have order 6
> twists" remark (this seemed to have been copied ad verbatim from the [BD18] paper).

I greatly appreciate the pointing out.
I couldn't find that it was a copy because it was written by the
previous author.
I have rewritten the entirety of the relevant sentence.


> Section 2.4, 4th para: it would be good to mention that parameter t must be 1 (mod 3),
> since otherwise p is not an integer.

Thank you for your suggestion!
We revised the part pointed out according to your comments.


> Section 2.5: the representation conventions are highly confusing, esp. for extension
> fields. Why not define everything in terms of a prime field GF(p) and extension field
> GF(p^t), with fixed irreducible polynomial f(z) of degree t over GF(p)? This has been
> successfully used with elliptic curve specifications (NIST, ISO, ANSI, BSI) not
> tailored to pairing based crypto. This would also avoids questions that now immediately
> come up (such as whether defining GF(p^{d'}) in terms of GF(p^{d}) and "inductively
> applying the above convention" does yield an unambigous definition. Since all finite
> fields of fixed size are isomorphic, it would be much easier to stick to the standard
> way of doing this. This would also avoid messy tower of extension field arguments and
> messy representations of elements hereof (e.g., in Section 4.4). See also Appendix J on
> data conversions of the lwig draft referenced in this draft. As final note, the data
> conversions in that lwig draft require specifying bit/octet encodings (which, in the
> pairing case, seem to be most-significant-byte-first (MSB) and most-significant-bit->first (msb).

Thanks for your comments.
Your proposed extension field seems to be simple, but there are many
different ways to construct an extension field GF(p^12).
Since BN254 with the embedding degree 12 was a major parameter,
efficient construction methods for GF(p^12) have been researched.

>From the viewpoint of practical use, we adopted the construction
method with (Fp-Fp2-Fp6-Fp12) using tower fields , which has also been
used in implementations such as mcl library.
In addition, we use MSB-first (the big-endian encoding), so we've written that.


> Section 3.1, 4th para: it is unclear what the meaning of "best known" is: is this
> "best-known" (i.e., most well-known) or "simply the best"? Given the description, the
> first meaning should be the correct one…

Thank you for your comments!
We revised the part pointed out according to your comments.


> Section 3.2: what is missing is a section that actually describes the attack, rather
> than simply plugging in some implied numbers based on a paper (presumably [BD18]). Why
> not add some verbiage that explains this in simple but roughly accurate terms ("The
> exTNFS Attack", or, better, "Attacks on DLP over Low-Degree Extension Fields", or even
> better, "Solving the DLP in Finite Fields" (there has been lots of progress there for
> mid-size base fields too)). This is a CFRG document, so one would expect something that
> provides insight, rather than simply a bombardment of tables, some selection criteria,
> and a filtered list. Wouldn't the objective of this whole effort be to educate the CFRG
> audience on pairing-based crypto, rather than (say, obtaining an RFC number from an SDO
> and marketing this as an implied "authoritative" approval stamp)?

Thank you for your suggestion!
We agreed with your comments and added an explanation of the attack.


> Section 3.2: I remember that Francisco Rodriguez-Henriquez (fix name in references)
> presented attacks at the CHES 2013 rump sessions, where question was whether this
> spelled trouble for pairing-based crypto. While I do not have his presentation then on
> file, it may be good to dig this up or ask him, and contemplate on wider implications
> of DLP progress in general (see also first general review remark).

Thanks for the reference information.
On the other hand, the rump session is not a peer-reviewed
presentation, so it is difficult for us to refer to it.
Also, since CHES 2013 is before exTNFS (Kim's attack) was proposed, we
believe that if the impact of Francisco's presentation is significant,
it would be carried over into the research of exTNFS.


> Section 3.2, 2nd para: A natural question is what one could say about DLP complexity
> for GF(p^k), in terms of dependency on p and k. Unfortunately, this section does not
> provide any insight on this (it only provides a single numerical value for BLS48
> curves, without any context). I would suspect the reader audience would appreciate such
> insight, without need to wed through a whole forest (6 1/2 pages: far too much
> reference stuffing!) of references by himself without any guidance as to whether this
> would be time well-spent or lost.

Thank you for your comment.
As you point out, there are a lot of citations, but we would like to
summarize based on a fact shown in related papers.
The reason is to avoid mistakes and misleading for the readers by
re-writing the content of the paper.
Therefore, we believe that a description of the impact of the attack,
which is a fact shown in [BD18], is sufficient for the draft.


> Section 4: as stated before, the selection criteria seem somewhat arbitrary, since
> conflate specification text, libraries, with actual deployment. Moreover, the most
> important criteria should probably be security and speed given particular security
> strength, and potential support for finite field arithmetic on platforms (speaking of
> which: why not devote a section on whether one can actually implement GF(p^k) securely
> using finite field libraries, including modular reductions, side channels, etc.?). The
> term "adoption status" seems, in any event, misleading.

Thanks for your comment.
This comment has already been answered as General Remarks by e-mail.


> Section 4.1, Table on pp. 12-15: if one strikes out domain parms rendered immediately
> suspect by the exTNFS paper on DLP, this kills off 8 out of 10 entries on p. 12 (and
> far more if one stikes out suspect values accross the entire table). This makes me
> wonder what the technical reason is for including this entire table. To the casual
> reader it now suggests that there are huge numbers of implementations out there,
> whereas - perhaps - most of those should be switched off immediately...

Thanks for the suggestion!
Based on your suggestion, we have removed the parameters of the
100-bit security level from Table 1.
On the other hand, we have summarized the parameters removed from
Table1 as a separate table and showed them in the appendix, because we
believe that it would be a useful information for implementers to
indicate in which libraries the parameters of the 100-bit security
level are in.

The problem with the size of Table1 has been pointed out by other CFRG
members, but we haven't found a solution to it.
We feel that your suggestions have made more readable and we greatly
appreciate you.


> Section 4.2.1: The extension field GF(p^{12}) can also be described via GF(p) and
> degree-12 polynomial f(w):=(w^6-1)^2+1. This would allow using simple conventions used
> in Lidl et al's finite field book [2]. It also allows description of an element x of
> GF(p^{12}) as vector (x_{11}, ..., x_1, x_0) of coefficients of GF(p) with this
> irreducible polynomial. Note here that u+1:=w^6 and v:=w^2, so one can easily
> internally use the more complex tower field stuff in the draft, while sticking to
> simple and easy to maintain standard constructions (known for 2 centuries) for
> specifications (so, nobody looses out if one has a slim interface that does this
> conversion back and forth, if necessary).

Thanks for your suggestion.
Please refer to the answer to the fifth technical comment regarding
the reasons for adopting the construction of the extension fields.


> Section 4.2.1, bottom of p. 18: shouldn't the cofactor h be such that h*r= # E'(GF
> (p^2))? {please also fix Et and use E' notation as elsewhere in the draft}

Thank you for your comment!
We revised the part pointed out.


> Section 4.2.1, parameter b' (bottom of p. 19): if one uses the complicated tower
> construction, why then not also mention the value of u in the enumeration? Is one
> actually sure this value is uniquely defined (e.g., I did not check but wondered what
> would happen if one replaces u by -u in the tower construction)? Same with end of
> Section 4.2.2...

Thanks for your question.
In our draft, the parameter u is given as a polynomial, because it is
the element in the extension field.
That is, it does not have a numerical value.


> Section 4.2.2, 5th para: the statement "CP8_544 is more efficient" is hard to interpret
> without context (e.g., half the cost, cost-1, cost - o(log log log n)).

Thanks for pointing out.
We have added the results of comparing the performance between BN462
and CP8_544, based on the paper.


> Section 4.2.2, bottom of p. 20: with parms BN462, why not simply introduce base point
> G, parameter n, h, etc., once and for all in Section 2.1, without trying to repeat
> their definition in Section 4.2.2 (and later sections)?

Thanks for your suggestion!
Based on the suggestion, we modified the description of terminology
and deleted the apparently repeat definitions, such as parameter n, h,
etc.


> Section 4.2.2, top of p. 21: the formula for h seems incorrect (G2 is defined over GF
> (p^2), whereas the formula refers to a curve defined over GF(p^8).

Thank you for your comments!
We revised the part pointed out.


> The security consideration section (Section 5) is rather slim: (speculation on my side)
> is the reason to label this draft as "experimental" that design strength vs. actual
> strength is somewhat in limbo due to progress on DLP problem? Why suddenly squeeze in a
> point validation routine if no context is given at all of where and how pairing based
> crypto is used? Wit point validation, what if an octet representation is outside GF(p)
> boundary? (while the forelast para seems to imply an attack one is completely left in
> the dark what is at stake here). Not sure whether it is the role of CFRG documents to
> legitimize "BN254 use ... to keep interoperability". The end of the first para ("as of
> 2020, as far as we know, there are no fatal attacks that significantly reduce the
> security of pairing-friendly curves after exTNFS") is entirely non-reassuring to me: it
> is only four years after the DLP attack that necessitated to strike out half of the
> entries in the table earlier on in the paper, not that many people work on pairing
> -based algorithmic cryptanalysis in the first place, etc., etc. Where does this
> confidence come from (shouldn't one be more modest here, technically speaking???). The
> Cheon attack is not explained and cannot be evaluated at all, since no context on
> elliptic arithmetic is given at all in the draft.

Thanks for your comments!
There are multiple items in the comment, and we will answer below.

Regarding the comments related to the draft type "experimental",
please be assured that we will discuss the change to "informational"
with the CFRG chairs.

The application of pairing is shown in Section 1, so we have added a
citation of Section 1.

As you pointed out, the description allowing the use of BN254 is
inappropriate as an IRTF draft, so we have removed that statement.

As for attacks outside GF(P) boundary of the octet string, there are
fears of the signature forgery.

Since you concerned about the description of "as far as we know...",
we revised it more properly.
We write our draft based on the investigation result of the conference
papers, so we revised it as "as far as we've investigated the top
cryptographic conferences in the past...".

We added the explanation of the Cheon algorithm.


> Secion 5, 3rd-last para: Why would the Montgomery ladder suddenly come to the rescue to
> salvage side channel resistance? Why refer to RFC 7748: whereas pairing-friendly curves
> are all Weierstrass curves, the curves in RFC 7748 are all Montgomery curves with
> completely different underlying detail on differential-addition chains). It seems that
> an entire section should be devoted to how implementations coul avoid SCA attacks, esp.
> since some operations take place in huge extension fields GF(p^t)...

Thanking for pointing that out!
Thanks to your point, we found that the readers may not immediately
understand by RFC 7748 that the montgomery ladder can be applied to
Weierstrass curves.
So we decided to refer to another reference that specifies the
detailed algorithm of montgomery ladder.


> Appendix C seems to convey a particular encoding used by ZCash. I don't think it is the
> role of CFRG to make those the standard way of doing things. This being said,
> technically that representation is a tiny tweak of what the SECG1 specification already
> stipulated in 2001 (with SEC1, one can extract the affine/compressed encoding of an
> affine point and whether this relates to the point at infinity from the leftmost octet
> (0x04, 0x02 or 0x03, vs. 0x00), which more or less 1-1 corresponds to the (C_bit,
> I_bit, S_bit) combinations. If so, reinventing yet another representation is hard to
> defend.

> The parity bit notation for finite fields is highly non-standard, compared to, e.g.,
> what has been standard usage with compressed points for curves over prime fields or
> binary extension fields. Even if this would have some uses, why not defining things
> once and for all for all extension fields of an odd prime field, so that this is a
> simple extension. See also Appendix H of [1] (parity function for any field GF(p^k),
> where p odd). This should also help in limiting side channel leakage from the first
> -half vs. last-half of [0,p-1] test.

Thanks for your comments!
We do not wish to propose the ZCash representation as a new convention
in our draft.
Our motivation is to describe the ZCash representation as a reference
to implementers because it is the data convention that has been
adopted by many BLS signature implementations.

Therefore, to avoid any misunderstanding to the reader, we have
clearly written that ZCash representation is a tiny tweak of SEC1
representation.
In addition, for your reference, we would like to mention that the
parity bit representation is not entirely non-standard, as it is
proposed in the IEEE document.
IEEE Std 1363a-2004 gives serialization and deserialization procedures
for curves over GF(p^m), and the ZCash spec is also very roughly
similar to those.


(Editorial Comments)

> Section 2.1, first para: replace "F_q" by GF(q), stipulate that extension degree n>0.

Thank you for your comments!
We revised the part pointed out according to your comments.


> Section 2.1, first para: with defining equation, use more common domain parameters a
> and b (i.e., lowercase instead of upper case). Elsewhere, do use common nomenclature
> used with NIST, ANSI, SECG, ISO for 2 decades, including n for prime-order subgroup, h
> for co-factor, mention irreducible polynomial f(z) with extension field, denote fixed
> base point by P (instead of BP), etc. If one wishes, refer to Appendix B.1 of [1].

Thanks for your suggestions.
According to your comment, we changed the domain parameters "A" and
"B" to "a" and "b" because a lot of documents related to ECC use "a"
and "b".
The "a" was used to represent an another parameter, so we also changed
the related parts.
On the other hand, we are sorry, but we did not change the parameter
"BP" that represents the base point BP to P, because we would like to
use P as a variable to represent an arbitrary rational point.


> Section 2.1, 2nd para: "point on" should be "point of".

Thank you for pointing out.
I'm sorry, but some standard specifications and textbooks use "on", so
I would like to follow them.

RFC6090: Fundamental Elliptic Curve Cryptography Algorithms
https://tools.ietf.org/html/rfc6090

Hashing to Elliptic Curves
https://tools.ietf.org/pdf/draft-irtf-cfrg-hash-to-curve-09.pdf

SEC 1: Elliptic Curve Cryptography
https://www.secg.org/sec1-v2.pdf

Rational Points on Elliptic Curves (Undergraduate Texts in Mathematics)
J. H. Silverman, J. T. Tate
https://www.amazon.co.jp/Rational-Elliptic-Undergraduate-Mathematics-English-ebook/dp/B00YPPBZYG

Handbook of Elliptic and Hyperelliptic Curve Cryptography
H. Cohen et al.
https://www.amazon.co.jp/dp/B00I60LZPA/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1


> Section 2.1, first/3rd para: isn't it simpler to define curve over GF(q) and then
> introduce curve with same domain parms, but then defined over extension field GF(q^k)?

Thank you for your suggestion!
I'm sorry, but I think there is not a big problem because this part
has passed Expert Review.


> Section 2.1, 3rd para: "group law which" should be "group law that", "reflection about
> x-axis" should be "reflection around x-axis", with "unique third point of intersection
> [R]" (i.e., give this a name, here R), with [a]P, stipulate that [0]P is the identity
> element and that [-a]P=-([a]P), etc.

> Section 2.1, terminology: fix E(F_{q^k}) (i.e., add paranthesis), fix that this refers
> to GF(q^k)-rational points (rather than GF(q)-rational points, same with cardinalities.

> Section 2.1, terminology: with co-factor h, doesn't one need gcd(h,n)=1 (so, as to
> ensure unique order-n subgroup)?

> Sectioon 2.2, 2nd para "is called embedding degree of E over GF(q)" (i.e., add curve
> and field over which this is defined)

> Section 2.2, 2nd para: the term "twist" is not defined (but often used elsewhere in the
> draft), neither is the term GF(p^k)* (nonzero elements of GF(p^k).

> Section 2.3, 2nd para: replace "prime p" by "prime number p (where p at least five)".

> Section 2.3, 3rd para (top of p. 8): write "the multiplicative group..." or, better
> still, simply state that b is a primitive element of GF(p) (and add this to
> terminology).

> Section 2.4, 4th para: "parameterized" should read "parameters".

> Section 3.1, 3rd para: "paiting-based" should be "pairing-based" (i.e., fix the typo
> "t" --> "r").

> Section 3.1, 4th para: "to solve" should read "for solving".

> Section 3.2, 1st para: "the security level(s)" (i.e., make plural), "... correspond"
> (i.e., use corresponding verb conjugation).

> Section 4.2.1, 4th para: "categorized as M-type" ("as" instead of "into").

Thank you for your comments!
We revised the part pointed out according to your comments.


> Section 4.2, 2nd para: reword "more prudent option" as "more conservative option".

Thanks for your comment.
I'm sorry, but this sentence was suggested by the Expert Reviewer, so
I'd like to keep this expression.


--------



-- 
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.

E-Mail: [e-mail]