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

Rene Struik <rstruik.ext@gmail.com> Thu, 12 November 2020 01:12 UTC

Return-Path: <rstruik.ext@gmail.com>

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 ECBEB3A129D
for <cfrg@ietfa.amsl.com>; Wed, 11 Nov 2020 17:12:46 -0800 (PST)

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

X-Spam-Flag: NO

X-Spam-Score: -2.1

X-Spam-Level:

X-Spam-Status: No, score=-2.1 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,
NICE_REPLY_A=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key)
header.d=gmail.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 MATFBzUzQc-A for <cfrg@ietfa.amsl.com>;
Wed, 11 Nov 2020 17:12:44 -0800 (PST)

Received: from mail-qt1-x836.google.com (mail-qt1-x836.google.com
[IPv6:2607:f8b0:4864:20::836])
(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 D37FB3A129F
for <cfrg@irtf.org>; Wed, 11 Nov 2020 17:12:43 -0800 (PST)

Received: by mail-qt1-x836.google.com with SMTP id 3so2902217qtx.3
for <cfrg@irtf.org>; Wed, 11 Nov 2020 17:12:43 -0800 (PST)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=subject:from:to:references:message-id:date:user-agent:mime-version
:in-reply-to:content-transfer-encoding:content-language;
bh=BFaRLUHKEjpvju7G9O7zIzMkl+LkML493m3bT+TtIbY=;
b=OFsj+YS3TLONybeBBzEvPN3xqN7KsWB2bb/CoyP3qdLnzDnOdOBvq0F9JH3Mo1JvEd
LyqLCOmGY0d81iBv+YSarDZkceGMedahtssjU/F8qcxwWoLZLEP8PFTTY5LQ/G7quJl5
Ro3SSEtt4nA5RqRpcNaHtHEkFn2PGKGNRuLXJ1MEBUbdRvTkt9OgKwxijjE6gZRhqGer
M9TbHV2P/13Vqw8HO3ve5XF4DzU55j000gfQh6NJ2tNP+HwEMCCvgHNZzi2IEOb+eN5+
UScVKEpU5bB2Lno+uKyMQy9y2bBKN5pwgVP+A49hm7LwJoFxUyj+7237qqIPdFDQiHfj
oVvg==

X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:subject:from:to:references:message-id:date
:user-agent:mime-version:in-reply-to:content-transfer-encoding
:content-language;
bh=BFaRLUHKEjpvju7G9O7zIzMkl+LkML493m3bT+TtIbY=;
b=JmrJR3dQvxrHf0/I60PfnW1QRNkBCYl92VWCVAUVd6euPC0Z3cBX660k/3cE6B3oxM
JIRk52Et60T1BV1af+PYclMD4yXSQzmnk4VDl6q5Ju6C08Cv2vWCaXnCoLM9BE9oTMOG
c91sfycSTiZI2XwQt48aOScX+/ZQ8YXdRQlmVNLDJr24gtGvABE5Nb+oWwPHu80sxjQC
P2EWQ492OxoLzmTiXLKPZ8AOqkvyBzI8GfExvzAxl4mysrreNtDXkW1RqBNGEqvuu/+c
Iac3WlxoApRzAUJ2JJGPJ8aXM7VxHuake5v+S527f39Lzw/YnnFcT/4eKP1awbuk0nQC
GBKw==

X-Gm-Message-State: AOAM530+rjXhUtan07wJVXkOgjY0YDR6NSmLPfPHGJ/qgRQYkwyKW+Yq
Xz/sfAhx1WOrzmecH/nXC8oCHr1fAes=

X-Google-Smtp-Source: ABdhPJzK3qXSBVYOkEnc6ZRtUZXA9/5smEfUdtq5yLFuQZNDzd49jWjkqkgNvd5mrQn8OaJSVFBKNQ==

X-Received: by 2002:ac8:1493:: with SMTP id l19mr25678659qtj.198.1605143561685;
Wed, 11 Nov 2020 17:12:41 -0800 (PST)

Received: from ?IPv6:2607:fea8:8a0:1397:88f6:1262:2298:b36f?
([2607:fea8:8a0:1397:88f6:1262:2298:b36f])
by smtp.gmail.com with ESMTPSA id p73sm4127139qka.79.2020.11.11.17.12.40
for <cfrg@irtf.org>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Wed, 11 Nov 2020 17:12:40 -0800 (PST)

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

To: "cfrg@irtf.org" <cfrg@irtf.org>

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>

Message-ID: <99c265ad-728d-fdfa-7eb1-99ac4b611f37@gmail.com>

Date: Wed, 11 Nov 2020 20:12:38 -0500

User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.4.3

MIME-Version: 1.0

In-Reply-To: <c9cc5bf6-e08f-9beb-d883-da96680a1d1a@gmail.com>

Content-Type: text/plain; charset=utf-8; format=flowed

Content-Transfer-Encoding: 8bit

Content-Language: en-US

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/WoYI0m3Q-xrminEsmjQRUWVfqzc>

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 01:12:47 -0000

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] 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