Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-curves-07

[Yumi Sakemi <[e-mail]>]

Dear  Stanislav and CFRG members

Thank you for announcing the comments from Rene.
After the RG Last Call period, some CFRG members  gave us a lot of comments.

We appreciate Rene, Armando, Dan Boneh, and Michael Scott for their comments.

Could you wait some time because we would like to consider how to deal
with it in the draft?

Best regards,
Yumi

2020年7月13日(月) 18:18 Michael Scott <mike.scott=[e-mail]>:
>
> Perhaps some of the  reassurance sought on the difficulty of the DLP as it arises in the context of pairing-based cryptography might be found in the very last paragraph of [BD18] https://eprint.iacr.org/2017/334.pdf Appendix B
>
> "Practical improvements will continue to come but they will modify only the o(1) term. A hypothetical algorithm which would beat SexTNFS needs to produce relations faster than by enumerating all elements of a sieving space, as it happened in small characteristic with pinpointing, or it would have to completely abandon the NFS diagram. Such an algorithm would be a great discontinuity, comparable to a possible sub-exponential algorithm for DLP on elliptic curves.  "
>
> Mike
>
>
> On Mon, Jul 13, 2020 at 12:08 AM Rene Struik <[e-mail]> wrote:
>>
>> Dear colleagues:
>>
>> Please find below my review of the pairing draft. If this does not display well, please send me an offline note and I can send you the original text file (before cut-and-paste into this email).
>>
>> I hope this helps.
>>
>> Review of draft-irtf-cfrg-pairing-friendly-curves-07
>> Reviewer: Rene Struik
>> Assessment: not ready
>>
>> Summary:
>> The draft provides domain parameters for a few curves used with pairing-based cryptography and provides some test vectors.
>>
>> General remarks:
>> a) While the draft suggests multiple times that the exTNFS attack (2016) negatively impacted the bit-security level of various proposed domain parameter sets for pairing-based curves, it does not provide any detail on this attack itself, nor any reassurances that potential extensions of these (only 4-yr old!) attacks on the general discrete logarithm problem of composite degree extension fields GF(p^t) for small composite t>1 would not be in the cards. This diminishes trust in the claimed security of these curves and their "fitness for use" in practice. the only use of these attacks is simply providing lengthy tables with claimed revised security levels. Why should one have confidence in this, do advances in solving the DLP in small degree extension fields provide the kiss of death for pairings (or if not: why not?), etc?
>> b) The draft has 6 1/2 pages of references and 3 1/2 pages of tables of "adopted parameters" on a total of 27 pages of main body text. It seems one should be able to considerably prune both tables and references (which now come across as unwieldy). A good starting point may be to consider that availability of a library or standardization does not necessarily imply that schemes are actually deployed.
>> c) It is unclear what motivated change in co-authorship of this draft, e.g., when considering changes between rev04 and rev07 of this draft. It seems more customary to credit minor contributions in the acknowledgement section than by change of authorship.
>> d) Lots of specification details seems adhoc and even motivated by a particular company's conventions. For CFRG, it may be more appopriate to specify curves, finite fields, and objects that live herein, in a more systematic way, rather than reinventing the wheel, thereby fostering reuse and maintainability.
>> e) I am curious why this draft's intended status is "experimental" (vs. "informational", as is far more common for IRTF documents).
>>
>> Detailed 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)?
>> 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.
>> 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).
>> 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.
>> 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).
>> 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...
>> 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)?
>> 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).
>> 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.
>> 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.
>> 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...
>> 12) Section 4.1.2: once again, I am wondering why there is so much emphasis on libraries here. Isn't this an IRTF/CFRG document?
>> 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).
>> 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}
>> 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...
>> 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)).
>> 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)?
>> 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).
>> 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.
>> 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)...
>> 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.
>>
>> Editorial comments:
>>
>> 1) Section 2.1, first para: replace "F_q" by GF(q), stipulate that extension degree n>0.
>> 2) 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].
>> 3) Section 2.1, 2nd para: "point on" should be "point of".
>> 4) 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)?
>> 5) 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.
>> 6) 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.
>> 7) Section 2.1, terminology: with co-factor h, doesn't one need gcd(h,n)=1 (so, as to ensure unique order-n subgroup)?
>> 8) 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)
>> 9) 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).
>> 10) Section 2.3, 2nd para: replace "prime p" by "prime number p (where p at least five)".
>> 11) 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).
>> 12) Section 2.4, 4th para: "parameterized" should read "parameters".
>> 13) Section 3.1, 3rd para: "paiting-based" should be "pairing-based" (i.e., fix the typo "t" --> "r").
>> 14) Section 3.1, 4th para: "to solve" should read "for solving".
>> 15) Section 3.2, 1st para: "the security level(s)" (i.e., make plural), "... correspond" (i.e., use corresponding verb conjugation).
>> 16) Section 4.2, 2nd para: reword "more prudent option" as "more conservative option".
>> 17) Section 4.2.1, 4th para: "categorized as M-type" ("as" instead of "into").
>>
>> Ref:
>> [1] draft-ietf-lwig-curve-representations-10
>> [2] R. Lidl, Niederreiter, "Finite Fields", Cambridge University Press, ...
>>
>> On 2020-06-19 1:50 p.m., Stanislav V. Smyshlyaev wrote:
>>
>> Dear CFRG participants,
>>
>> This message is starting 2 weeks RGLC on draft-irtf-cfrg-pairing-friendly-curves-07 ("Pairing-Friendly Curves"), that will end on July 4th 2020. If you've read the document and think that it is ready (or not ready) for publication as an RFC, please send a message in reply to this email or directly to CFRG chairs ([e-mail]). If you have detailed comments, these would also be very helpful at this point.
>>
>>
>> P.S.: The review on behalf of Crypto Review Panel was done by Chloe Martindale, the comments have been addressed by the authors of the draft, see https://mailarchive.ietf.org/arch/browse/crypto-panel/
>>
>>
>> Thank you,
>>
>> Stanislav, for CFRG chairs
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>> --
>> email: [e-mail] | Skype: rstruik
>> cell: [phone] | US: [phone]
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg



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

E-Mail: [e-mail]