Comments from Rene during the RGLC (Detaild Comments)

[yumi-sakemi]

Detailed comments from Rene (CFRG members) are shown as follows.

https://mailarchive.ietf.org/arch/msg/cfrg/pW71h3yUETnqedHsH0m3rwzPnm4/

[Tsune3110]

OK!

This is a cross-check as a co-author.

[Tsune3110]

OK!

This is a cross-check as a co-author.

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

[yumi-sakemi]

(Reply Comments)

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

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