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

"Stanislav V. Smyshlyaev" <> Mon, 13 July 2020 15:37 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 2392A3A133F for <>; Mon, 13 Jul 2020 08:37:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id YlJz0ScYm7Wc for <>; Mon, 13 Jul 2020 08:37:14 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::235]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 938263A14DD for <>; Mon, 13 Jul 2020 08:36:45 -0700 (PDT)
Received: by with SMTP id h19so18362024ljg.13 for <>; Mon, 13 Jul 2020 08:36:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=+5FtanPh5l4mYgBFwo3CmJVr2nC0UKS+ZbZU9inibjc=; b=cC3eIxRfpFnMqqBgcrEPttTIZlCs8ICHJoLhaawQaP7CRZAIV8tdXrsfFIQ5pASbZw brBLVmUUO+t6x1YEtBNccpSWwTzZVSpGK61SIJp8TCQ9lGlws/iYRpkkV6eRArlkPev/ /OZNYvbCyYdR430OQJ5U+Y4UbBDQC/zGgSY5US99pZp3gF42ZDS30NIT54ullIKYQ6P6 6h5L8EEg4r0f+KoeFDpNmwaJTLz9LDOzed78hBmgZPDeNHuKZ34fsIS2KQ7lG/tPRKBX S3yYndzFdg4gCDHRQPh+Q4c9jAGyLTri4ZBEV1Kxvs0pR6f5DJ2LagfRu3LfeFKdaQTV z17g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=+5FtanPh5l4mYgBFwo3CmJVr2nC0UKS+ZbZU9inibjc=; b=bzlX6TJiRSPTcbaIpt44QsD1fvqWYryLuMeeMCjsOFSeZ5emvS5yzohtOc4g1tj85i IN0cSitTgY9NBb1wiaBsOAc8HJ3d9VP09WH4AL/UlgDVLQuCsclZp8NXrZB1Yg400mhs BgwIE2K6/51BEJP2DiKXSP5RSUMnY1+LBqp/pLlOQyWiB3Ln+lX3Y9NCjxX3lTWz9Hse yPxTZb7RCS2q/ND3bfuvDQs5ULOjowGXhp+XkG6CZ+22cP+XUd6w9N/P1jCxH7v/0/Es SRDiBIiNKCHMP660LGpwqYcvgJTz2s9nEo4QWuZlvNHdOe7NNx9IqLtGY5KmmkY+F5Kv c8uw==
X-Gm-Message-State: AOAM530+qFI1F7ieRMG011F0ofsE6IMNeeqRFGrI7OlLh1GfLvmovQm+ r4JFlaMaB+oNMipMskJ5i4Pig9xs0Ht9cNk/kQHVhQ==
X-Google-Smtp-Source: ABdhPJylqKzPqTKrUBrSw7yekQlzhFZR3ogFVTL4+Vwwzrf2hxZJNAxJmt0ELZktoYkk+t8qF+9oc9KEdRZYIga+zsI=
X-Received: by 2002:a2e:9415:: with SMTP id i21mr159350ljh.196.1594654603564; Mon, 13 Jul 2020 08:36:43 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <>
In-Reply-To: <>
From: "Stanislav V. Smyshlyaev" <>
Date: Mon, 13 Jul 2020 18:36:32 +0300
Message-ID: <>
To: Yumi Sakemi <>
Cc: CFRG <>, "Riad S. Wahby" <>, Tetsutaro Kobayashi <>
Content-Type: multipart/alternative; boundary="0000000000002f5a1305aa5475cd"
Archived-At: <>
X-Mailman-Approved-At: Mon, 13 Jul 2020 10:05:51 -0700
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-curves-07
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 13 Jul 2020 15:37:17 -0000

Dear Yumi,

Yes, please take your time to address the concerns.


пн, 13 июля 2020 г. в 18:12, Yumi Sakemi <>:

> 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 <
> >:
> >
> > 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]
> 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 <>
> 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 (
> 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
> >>
> >>
> >> Thank you,
> >>
> >> Stanislav, for CFRG chairs
> >>
> >>
> >> _______________________________________________
> >> Cfrg mailing list
> >>
> >>
> >>
> >>
> >> --
> >> email: | Skype: rstruik
> >> cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
> >>
> >> _______________________________________________
> >> Cfrg mailing list
> >>
> >>
> >
> > _______________________________________________
> > Cfrg mailing list
> >
> >
> --
> Yumi Sakemi, Ph. D.
> Lepidum Co. Ltd.
> E-Mail:
> _______________________________________________
> Cfrg mailing list