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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear Yumi,

Yes, please take your time to address the concerns.

Regards,
Stanislav

пн, 13 июля 2020 г. в 18:12, 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]
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>