### Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pairing-friendly-curves-08.txt

Yumi Sakemi <yumi.sakemi@lepidum.co.jp> Thu, 12 November 2020 07:16 UTC

Return-Path: <yumi.sakemi@lepidum.co.jp>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id F36C13A14BB
for <cfrg@ietfa.amsl.com>; Wed, 11 Nov 2020 23:16:12 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -1.899

X-Spam-Level:

X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001]
autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=lepidum-co-jp.20150623.gappssmtp.com

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id hrPgKdb6-TMG for <cfrg@ietfa.amsl.com>;
Wed, 11 Nov 2020 23:16:09 -0800 (PST)

Received: from mail-ot1-x330.google.com (mail-ot1-x330.google.com
[IPv6:2607:f8b0:4864:20::330])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 190DE3A14B9
for <cfrg@irtf.org>; Wed, 11 Nov 2020 23:16:08 -0800 (PST)

Received: by mail-ot1-x330.google.com with SMTP id a15so4684506otf.5
for <cfrg@irtf.org>; Wed, 11 Nov 2020 23:16:08 -0800 (PST)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=lepidum-co-jp.20150623.gappssmtp.com; s=20150623;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc:content-transfer-encoding;
bh=Y5R/rxuNO1/MMtLpK0ufZem72yZzRJeHWbq9ge2Z/R4=;
b=GBgXCCrIhl5ZnnGWQsC0lieUbbKxWewzwrVK2FNOgfXB51Uh5rbKeIsuLKEBm54mPN
lzAY81gulmmwrMGk9l+Q+ZscGrADIYPaqv9V7NwlLKnJY3d9pAdQlWBduiZQauZKWjV/
ha+SwThnA227aEF39HITlXkczfKviKIZMa8XTh7x/hHA1W57y/WEAvddPHMC8ASEO/J5
OfEsWwm3HAloSSoUmRRsXdEEtQfoKdVb0zzGr8y3hCuIUX6bFUJAGhGAgUjQUY/Z8tBf
dvKE1UXEryTPCCSSkmmfrC8e+LB2/HjoIhlmPW1vP8ayHJkZ23C3ur/FgIY6IfhdyOMe
FPCg==

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc:content-transfer-encoding;
bh=Y5R/rxuNO1/MMtLpK0ufZem72yZzRJeHWbq9ge2Z/R4=;
b=nPUgx1mNfXv5JBSrnaNisy01lBvfhvng1pcImEnl3MdnjpAj4vy/8waY6/B8wD5UqP
FTaUmwgAVsUTjLg0idRC9jdFSC5f2Ga+knH1gwuhrmikEq9JH9DTCVgL2RR+nIQV1BoW
8LIbMUepSVIM5zdXMJ68ee3QOIKDSz+dXkutSTWJf7YXtn8VAGgVzDoSCMqIyEkKVqH1
s5HrHMOccOO5oGxF9HXZzbMqbyjMaRDhQZdmwT6C6oyI4o3Abdx3AeCj9QK6iXTVhZLd
0nSehYM4v7/zCT8OePmB3KdNNbtKbm23AgG8GjxUqfgyBub2Sq/+1F21M4w9LXigMaU7
v/iQ==

X-Gm-Message-State: AOAM5337lUxnYh1a4xGcWs3l4nonSCmEbJi2cX0K+tiYnI8e3Z/lVWJf
Au3dXx5OHx0C8x8PXZGFG23vjKQ1OsxEmTfx0oSDmA==

X-Google-Smtp-Source: ABdhPJwdWzeo1pWKmHN6ui8UD7fAWiSRiBS5rWWKz3g7V6jCon3k9rVNo07nkH5t6yx5WUo/+0AFUtPf3kjsHWyzn3U=

X-Received: by 2002:a9d:23a6:: with SMTP id t35mr19476199otb.210.1605165367389;
Wed, 11 Nov 2020 23:16:07 -0800 (PST)

MIME-Version: 1.0

References: <160146973405.15802.8734665033319781394@ietfa.amsl.com>
<CAA4D8KbtBOFb=ampqBVH+3xRr9oR6ieV7feRhPpMqvyhWjYdFg@mail.gmail.com>
<CAMr0u6kpdjyHeCGBT-Y27RH_4wqX-DmSn5rDm0kd0w9kp4h4iQ@mail.gmail.com>
<CAMr0u6==PGwKZOQv52YfiAKPNA+U4Z7v=sT597pwzMzo2E=jNg@mail.gmail.com>
<b2846f5a-c000-e185-62d0-b1912d1f27dd@gmail.com>
<CAMr0u6nnkk0FQguafmjT5DBXEHDJJw=jfbxsSojC4vkaJ4ZEVg@mail.gmail.com>
<CAMr0u6n3PLNJ6w7M4RKfQ4g-2_acFqzJOTTY+oKEddtsYq7KLg@mail.gmail.com>
<CAMr0u6kLE5OFJjs4FVxP=NORFQ=S5xj7GQds6cFYuj4gJ7saag@mail.gmail.com>
<c37b509f-f8ed-e4f1-02a5-d414cbd618b7@gmail.com>
<13cdff98-c615-e640-53c3-05e1ee20a4f6@gmail.com>
<c9cc5bf6-e08f-9beb-d883-da96680a1d1a@gmail.com>
<99c265ad-728d-fdfa-7eb1-99ac4b611f37@gmail.com>

In-Reply-To: <99c265ad-728d-fdfa-7eb1-99ac4b611f37@gmail.com>

From: Yumi Sakemi <yumi.sakemi@lepidum.co.jp>

Date: Thu, 12 Nov 2020 16:15:55 +0900

Message-ID: <CAA4D8KbPA8X0tLu0nncATCm_uBK46nAR-y=MyD-pbBeowJFogQ@mail.gmail.com>

To: Rene Struik <rstruik.ext@gmail.com>

Cc: "cfrg@irtf.org" <cfrg@irtf.org>,
SAITO Tsunekazu <tsunekazu.saito.hg@hco.ntt.co.jp>,
Tetsutaro Kobayashi <tetsutaro.kobayashi.dr@hco.ntt.co.jp>,
"Riad S. Wahby" <rsw@cs.stanford.edu>

Content-Type: text/plain; charset="UTF-8"

Content-Transfer-Encoding: quoted-printable

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/MVDYsylq8VE9p-UqbYQ_nLdxW_8>

Subject: Re: [CFRG] [Cfrg] I-D Action:
draft-irtf-cfrg-pairing-friendly-curves-08.txt

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Thu, 12 Nov 2020 07:16:13 -0000

Dear Rene Thank you for your comments. I will check and discuss your comments with co-authors. Best regards, Yumi 2020年11月12日(木) 10:13 Rene Struik <rstruik.ext@gmail.com>om>: > > One more note: except for RFC 2119 and RFC 8174, none of the normative > references are, in fact, normative (since, e.g., referring to a > conference paper). Whether all 7 pages of informative references are > informative is in the eye of the beholder (it does hike up quotation > numbers, though). > > > On 2020-11-11 5:10 p.m., Rene Struik wrote: > > Dear Yumi et al: > > > > Please find below my review of > > draft-irtf-cfrg-pairing-friendly-curves-08. My apologies for the > > getting back to you this late. > > > > Best regards, Rene > > > > == > > > > Review of draft-irtf-cfrg-pairing-friendly-curves-08 > > Reviewer: Rene Struik > > Assessment: again, not ready (perhaps, ditch?) > > Note: page numbers in this review refer to rev-08 > > > > General comments: > > 1) It seems that at least half of my main technical comments (apart > > from editorials) with my review of the rev-07 draft have not been > > addressed. Moreover, it is somewhat hard to get back to the authors on > > the mailing list, since they buried their comment resolutions in a > > somewhat nebulous github structure. This makes it a little bit hard to > > get enthusiastic about doing yet another review. > > 2) It seems that the authors have not done any effort to disentangle > > technical specification, availability of libraries, and actual > > deployment (see my comment #01 of my rev07 review), where there still > > is a somewhat misleading tilt due to equating all these disparate > > things and where there is still an unusual prominence of company > > names, etc. Perhaps, some of this can be taken care of by including a > > section with "implementation status" (which disappears once this > > becomes an RFC), as other IETF drafts have done. Nevertheless, this > > would fly in the face of selection policies for pairing-based curves > > which are based on conflated notions. This begs the question what the > > purpose of this draft is. > > 3) The draft, as it stands, still contains lots of material that is in > > a state with much to be desired for. As an example, Appendix A > > contains quite a few errors (Ate pairing) and lacks sufficient > > explanatory context and Appendix C is such an adhoc hack that (I feel) > > this should never be endorsed by CFRG. For details, see some of my > > comments on rev08 (where I did focus on the appendices). > > 4) It may be best if CFRG ditches this document, since it still seems > > far off from being a useful document, written clearly so as to educate > > the CFRG and the wider IETF community. (Given the lack of feedback on > > this document over time, perhaps nobody would care.). Should CFRG > > still wish to give this draft a chance to become a CFRG-issued RFC, I > > believe it needs a major rewrite to get rid of nontechnical spin > > material. I also think it would be beneficial not to have yet more > > specifications come up with their own representations and procedures > > where there is no real technical justification for this. Should the > > authors wish to push this "as is", they could always pursue the > > "independent stream" for this (where one could argue that nothing can > > be changed). If this should be pushed furthr, I can imagine a slim > > draft, without umpteen tables and zillions of references, where one > > simply provides domain parameters and explains how mappings work > > without all the ads for libraries and start-up companies with > > non-empty github pages. > > > > For some detailed technical and editorial comments, see below. (I have > > more comments, but I think the below suffices to show this is far from > > ready.) > > > > I know this is not what authors want to hear and does not make me > > popular, but so be it. > > > > Detailed comments: > > 1) Appendix A: the description of the so-called line function is very > > unclear for non-pairing people (which I presume is most of the CFRG), > > where expressing this in a style resembling elliptic curve notation > > more would certainly help. Some suggestions: express the line function > > as Line_function(P1,P2,Q), where P1:=(x1,y1) and P2:=(x2,y2) are > > affine points of G2 (curve defined over GF(p^2)) and where Q:=(X,Y) is > > an affine point of G1 (curve defined over GF(p)), mapping to subgroup > > G_T of GF(p^k)^*. This allows expressing the number l if P1=P2 as > > l:=lambda:=(3*x1^2+a)/(2*y1), which is familiar in point doubling > > formulas for short-Weierstrass curves (where, here, domain parm a is > > zero) and, similarly, if P1<> (+/-) P2, as l:=lambda:=(y2-y1)/(x2-x1) > > (see, e.g., [3]). Here, it would also help explaining what happens in > > case of non-affine inputs (point-at-infinity) and why the output would > > be an element of the prime-order multiplicative subgroup G_T of > > GF(p^k)^*. > > 2) Appendix A, last para before A.1: one should mentions the image of > > the point-at-infinity under this Frobenius map. > > 3) Appendix A.1: this section seems to be full of ambiguities and > > errors: (a) should one assume the parameter t is the same as the one > > definining the prime p, etc.? (if so, please say so); (b) write > > c:=c0+c1*2+ ... + c_{L}*2^{L} and explain that c_L is nonzero and that > > the Ate pairing procedure works no matter the choice of the > > coefficients in the range {-1,0,1} (if not, much explanation is > > needed, since, e.g., c=0+1=2-1 may have different results; (c) fix the > > loop to "for i:=L-1 downto 0"; (d) replace the silly "|" language in > > the if condition "c_i=1 | c_i=-1" by "c_i nonzero" (you are writing > > this for humans, not for parsers); (d) the Line_function has three > > arguments, but in the call Line_function(T, ci*Q) it only has two: > > should this include P as third argument?; (e) how does one know the > > line function never receives non-affine points as input?; (f) the line > > with frobenius maps seems to compute Q1:=frob(Q); Q2:=frob(Q1) and, if > > so, doesn't one get Q2=frob(frob(Q))=Q since Q is a point of G2 and, > > thereby a point of a curve defined over GF(p^2)? > > 4) Appendix A.1: how does one know that f is never the zero element 0 > > (if so, it is not in GF(p^k)*)? > > 5) Appendix A.1: the Ate pairing seems to use integer c written in > > NAF-notation. If so, shouldn't one at least say something about side > > channels, in case the inputs or outputs of the Ate pairing are > > non-public parameters? What about the huge final exponentiation in > > GF(p^k)^*, where the exponent h:=(p^k-1)/r has an enormous size (~ > > p^{k-1})? (Note RS: I did ask about side-channels in my review of the > > rev07-draft [rev07-comment #10], but that comment was never addressed.) > > 6) Appendix A.2: the beginning of that section is virtually the same > > as Appendix A.1's, but misses some language (e.g., on "sum of > > (i=0,1,...,L)" --> equals c, order r --> of G1, etc. Remarks on some > > of the steps of the listed procedure similar to those with Appendix > > A.1 apply. > > 7) Appendix A would benefit from a much better explanation of the role > > of the Ate pairing in pairing-based crypto. Otherwise, this seems just > > loose sand, without context. (If the goal is to educate the CFRG > > audience about coolness of pairing-based crypto, why not provide > > sufficient detail to raise interest?; otherwise, why pursuing this > > draft?) > > 8) Appendix B: the relationship between elements of GF(p^k) and the > > output sequences (e_0,...,e_{11}), resp. (e_0,...,e_{47}) is not > > described in sufficient detail. > > 9) Appendix C: this appendix is so poorly written and the construction > > so adhoc that this should be abandoned right away (see also my > > previous comment in my rev-07 draft review (rev07-comments#21/#22). > > Here, simply observe that this point encoding only works for BLS12-381 > > and not for, e.g., BN462, purely because of poor design choices made. > > Please also see Note 2 of Appendix I.8 of > > draft-ietf-lwig-curve-representations-13 (which describes SEC1 > > representations, but now for any field of odd characteristic). Simply > > using the SEC1-encoding, where one squeezes-in the 1-octet identifier > > for affine points (0x04), point-at-infinity (0x00), and compressed > > y-coordinate (0x02 or 0x03) in the leftmost 2 bits of the tight > > MSB/msb-order representation of elements of GF(p), where the > > bit-length of p has two fixed bit positions for BLS12-381 and BN462 > > case does the job. > > 10) Appendix C: while I think this appendix should be ditched right > > away and replaced by a more systematic approach that, in principle, > > applies to all pairing-based curve domain parameters (see prevous > > comment), there are also some problems with the text itself, including > > (a) the high-level remarks are confusing and do not seem to contain > > any useful information, so might easily be removed; (b) The I2OSP and > > OS2IP functions in RFC 8017 do describe integer-to-octet-string and > > octet-string-to-integer conversions, but do not specify the > > bit-ordering (which is needed to describe the encoding of integers as > > bit-strings and vice-versa); (c) Step 2 (in Appendix C.1) seems to > > confuse specification and implementation (since seemingly aimed at > > machines rather than humans); (d) Step 3 (in Appendix C.1) seems to > > suggest that an element x=x0 + u*x1 of GF(p^2) is represented in the > > order "highest coefficient first", whereas in Section 2.5 this seems > > to be in the order "lowest coefficient first" (although this is hard > > to figure out due to the recursive definition in terms of towers of > > fields) - it is hard to figure out what "see discussion of vector > > representation above" refers to, since there does not seem to have > > been one; (e) Step 8 (in Appendix C.2) may result in output P:=(x,-y), > > where the second coordinate is a negative integer (and, thereby, not > > in the interval [0,p)). > > > > > > Editorial comments: > > 1) Appendix A, last para before A.1: this para refers to > > Barreto-Naehrig curves and should be moved to the beginning of > > Appendix A.1. > > 2) Appendix A, last para before A.1: why not expressing the Frobenius > > map in a more human-friendly way, e.g., frob(x,y):=(x^p,y^p), where > > one leaves the parameter p implicit? > > 3) Appendix B, l. 8: in "where u is a indeterminate", change "a" to "an". > > 4) Appendix B, l. 8: check for consistent naming of BLS48-581, etc. > > (underscore vs. dash language). Also elsewhere. BTW - it would help to > > add the curve name to section headings to make these easier to find, > > e.g., adding BLS12_381 to the title of Section 4.2.1, etc. > > 5) Appendix C, p. 49: replace "sign_F_p" by "sign_GF(p)", etc. > > 6) Section 4.2.1, last para: I am not sure what adding the new (in > > rev08) advertisement for another cfrg draft (hash-to-curve) adds to > > this document, since it seems to be just PR, without any context. > > Shouldn't one shy away from cross-marketing? > > > > Ref: > > [3] D. Hankerson, A. Menezes, S. Vanstone, Guide to ECC, Springer, 2003. > > > > > > [review posted to CFRG mailing list: Sun July 12, 2020, 7.07pm EDT] > > 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 (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, ... > > > > > > -- > email: rstruik.ext@gmail.com | Skype: rstruik > cell: +1 (647) 867-5658 | US: +1 (415) 287-3867 > > _______________________________________________ > CFRG mailing list > CFRG@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg -- Yumi Sakemi, Ph. D. Lepidum Co. Ltd. E-Mail: yumi.sakemi@lepidum.co.jp

- [Cfrg] I-D Action: draft-irtf-cfrg-pairing-friend… internet-drafts
- Re: [Cfrg] I-D Action: draft-irtf-cfrg-pairing-fr… Yumi Sakemi
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Armando Faz
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Ian Goldberg
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Yumi Sakemi
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Yumi Sakemi
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Rene Struik
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Rene Struik
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Yumi Sakemi
- Re: [CFRG] [Cfrg] I-D Action: draft-irtf-cfrg-pai… Yumi Sakemi