Re: [CFRG] Second RGLC on draft-irtf-cfrg-pairing-friendly-curves

Rene Struik <> Wed, 08 September 2021 19:26 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id A3D563A3404 for <>; Wed, 8 Sep 2021 12:26:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Status: No, score=-2.098 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, NICE_REPLY_A=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id jEVHzrCTJ-p9 for <>; Wed, 8 Sep 2021 12:26:24 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::836]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C69363A3407 for <>; Wed, 8 Sep 2021 12:26:23 -0700 (PDT)
Received: by with SMTP id t35so2893558qtc.6 for <>; Wed, 08 Sep 2021 12:26:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20210112; h=to:cc:references:from:subject:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=r9jibM6beqAb+yA27TjfVTAawwStt1IJvGr8GeuOk5Y=; b=od1P3mORYdSl7V2CmNtqUe4T+yMePxn7+2ODOwhiRm+IyYcLYU6p6uAypct3gciuJ1 bhDSOEUxXIrHop7RCs+N4UCr1GSZkgSbfgaQgMyPLNdVP82q+og7PUdtjrQ8c0LMpAZW VQ/vZ10cdqJjPmB8FwyLY2N9H6YxyyypWtFlVdZacM1QmRLWTRxVcBIpRkk1m6x5NnGN FJJKMNjWxQGsMYzCcPx3oIqruEzWhziHeKAQM3zYfNXB4Tk0d0jyQW8G8qm0tRTMkVym xy5xW5Y+k7VbdxMeQ/8YuXAchVmkXhExprxBfuAc+iBLx1NmnhRO3Uoeg2pzEFbw/20x jXVQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20210112; h=x-gm-message-state:to:cc:references:from:subject:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=r9jibM6beqAb+yA27TjfVTAawwStt1IJvGr8GeuOk5Y=; b=tD4xNLP8Cc21qsmfhuedebL7Fi/Ae3bFS2Lps6Qlbp9Cv071dqphO5h5zmvsy0ft/V FNwMkfnBDELKqBsuB9cMZ9zhAk7nt8Blu8ivYW83tCK8VnBpWbEPGC+FXCmPkeRmnRGW S4kGMNKgVwuXgajCWiu0CWv1GftEunw/NFwSW6rkjKkIxpgS0SppW5XOPHYJzRuEeiZ+ AC7WwkkP66se4qqtWUB/y+FMlvyULF1JDpeRgCu0ldaldpo0Neh1bH/LK2+42o68yb9y 5gPoGBpVOv2pGkGmOXZ3w2t6Ch71ZrWc+6UMEWyKXaBTHUUy0mF4NEcDkyiWTC9pS26T MqWw==
X-Gm-Message-State: AOAM533Ij3AYjEHZQ5aNcpx+dcnvE3dLXx9YxYXjQlBFrSJpj/oYWITl y7AC5w5odDguQK+Wktz59I8=
X-Google-Smtp-Source: ABdhPJxbN6iJkJ40HX631HAI8pnA6SI7y164pqstB7JbtMmS1H8BFyUUTSatCMYEThVOgVbccMLXxQ==
X-Received: by 2002:ac8:5f0b:: with SMTP id x11mr5278626qta.95.1631129180206; Wed, 08 Sep 2021 12:26:20 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:89c2:9fff:3d99:c0f2? ([2607:fea8:8a0:1397:89c2:9fff:3d99:c0f2]) by with ESMTPSA id a22sm2160003qtw.59.2021. (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 08 Sep 2021 12:26:19 -0700 (PDT)
To: "Stanislav V. Smyshlyaev" <>, CFRG <>
References: <>
From: Rene Struik <>
Message-ID: <>
Date: Wed, 8 Sep 2021 15:26:16 -0400
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <>
Content-Type: multipart/alternative; boundary="------------2920DB2FA6CFA993234C9334"
Content-Language: en-US
Archived-At: <>
X-Mailman-Approved-At: Thu, 09 Sep 2021 06:55:18 -0700
Subject: Re: [CFRG] Second RGLC on draft-irtf-cfrg-pairing-friendly-curves
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: Wed, 08 Sep 2021 19:26:31 -0000

Review of draft-irtf-cfrg-pairing-friendly-curves-10 (July 30, 2021)
Reviewer: Rene Struik
Assessment: again, not ready (final ditch or serious rewrite -- see "How 
further?" (i) or (ii) below.)
Note: page numbers in this review refer to rev-10

Remark (no review of rev-09 by me): The authors posted 
draft-irtf-cfrg-pairing-friendly-curves-9 (Nov 16, 2021), five days 
after I posted my review of rev-08 to the CFRG mailing list. They 
subsequently posted draft-irtf-cfrg-pairing-friendly-curves-10 (July 30, 
2021), just prior to the CFRG meeting during IETF-111. Since the rev-09 
draft was posted very close in time to my rev-08 review comments and did 
not yet include consideration of my rev-08 comments, I did not do 
another review at the time. The current review does consider what 
transpired to the draft since my earlier reviews on the rev-07 and 
rev-08 drafts (posted on Sun July 12, 2020 and Wed Nov 11, 2020, 
respectively). While the review is relative to rev-10, I briefly 
summarize my perception of what changed between rev-08, rev-09, and 
rev-10 of the draft.

Summary of (my perspective on) changes to the draft since rev-08:
a) rev-09 (posted Nov 16, 2021) seems to be a very minor update of 
rev-08 (25 lines changed/added [4]), mostly now including some verbiage 
as to which pairing-friendly curves the authors recommend.
b) rev-10 (posted July 30, 2021) again seems to be a slight update of 
rev-09 (96 lines changed/added [5]), mostly confined to more consistent 
curve naming (instead of using, e.g., both BLS12_381 and BLS12-381 to 
refer to the same object) and some small editorial changes to Appendices 
A, A.1, and A.2 (related to optimal Ate pairing description).

General meta remarks:
a) I posted earlier reviews of rev-07 and rev-08 drafts (copied at end 
of this rev-10 review). From past revisions (rev7 --> rev10) it is clear 
that those earlier reviews have not led to too much change at all (over 
the course of more than a year). Main problem here is that this is not 
really a conversation: There has hardly been (or is) any technical 
discussion on the CFRG mailing list, suggesting a very low energy level 
on this topic. Main interaction has been some tiny updates of a draft 
over a long time period, where the hope may have been for earlier 
reviewers to throw in the towel and get to the exit. I have seen some 
"blanket" support by one or two, but without any evidence that this 
support stems from a careful review of the draft at hand (since not 
accompanied by a single editorial or technical suggestion). While it is 
nice to support an area with potentially interesting applications (as I 
also do), this is (in my opinion) somewhat meaningless without 
considering and reviewing whether this same enthusiasm should also 
applies to offered details.
b) In my mind, quite a few comments articulated in my earlier reviews 
still stand (which are not repeated below). Nevertheless, just by 
considering rev-10, I noticed more technical questions that I did not 
already include in my previous reviews, e.g., regarding 
underspecification (see Details #3), and incompatible representation 
ideas between different CFRG drafts (see Details #1, #2), or the 
underlying philosophy (Details, #4). Moreover, field representations do 
not follow the representations in [7] the draft suggests (see Details #5).

How further?
I my mind, there are two possible next steps for this document:

i) ditch the draft (at some point, "enough is enough");

ii) narrow down the draft and make this into something that fits an IRTF 
group. This could, e.g., include
--- description of G1, G2, GT, and mapping e: G1 x G2 --> GT 
--- highlighting some motivating example (e.g., informally describe 
signing using pairing map, e.g., if repr: msg --> G1 map available, 
M:=repr(msg), Q2:=d*BP2, and S:=d*M, then 
e(d*M,BP2)=e(M,d*BP2)=e(M,Q2)). This would also make it clear why having 
a hash-to-curve function would fit into this space (link with 
hash-to-curve draft).
--- discuss which quadruples (G1, G2, GT, e) are "good", in terms of (a) 
efficiency; (b) cryptographic security; (c) implementation security;
--- describe how to represent all of this (bit/octet/field/curve 
conversions, etc.) in a non-adhoc way.
--- remove all advertising, marketing material, tables for table-sake, 
conflation of availability of libraries, actual use, etc.
Note RS: right now, I hardly see any discussion hinting at why, e.g., t 
with low-Hamming weight helps (a);  only "some" discussion re exTNFS 
(b); virtually "no" discussion re (c), even though already mentioned in 
my rev-07 review. From Detailed comments below it seems representation 
details are also lacking detail and consistency. This should all be fixed.

NOTE: I could have rewritten the entire draft along the above lines 
(ii), but - frankly - this is not my project. I am willing to help, but 
have hopefully already done so by the three reviews so far (no matter 
the lack of uptake). This could still be turned-around if the will to do 
so is there (where this could get the shape (ii) above within a few 
months of spare cycles outside normal work). The choice is yours and the 

Detailed comments:
1) Appendix C, p. 49: The sign function sign_GF_p is defined differently 
from the sgn0 function in the hash-to-curve draft (see [6], Section 
4.1), where in the first case this is set to 1 if the value is in the 
interval [(p+1)/2,p-1] and to 0 otherwise, while in the second case it 
is set to the parity bit (i.e., mod 2 value) of its representation as 
integer in the interval [0,p). Moreover, the sign function sign_GF_p^2 
for quadratic extension fields is defined "from-right-to-left" in this 
draft, whereas this is defined "from-left-to-right" in the hash-to-curve 
draft [6] (if one assumes polynomial coefficients to be ordered in 
increasing index order). {As an aside, the notation should probably read 
sign_GF(p) and sign_GF(p^2).}
This seems to unnecessary complicate applications that may wish to use 
both drafts (such as BLS signatures).
2) Appendix C, p. 49, Section 2.5, p. 10: Elements of a non-trivial 
extension field GF(p^m) are represented using a "towering fields" 
construction, which is generally different from (and inconsistent to) 
the representation of extension fields in the hash-to-curve draft (see 
[6], Section 2.1) {which uses a polynomial construction as 
GF(p^m):=GF(p)[x]/(f(x)), with f(x) a polynomial of degree m}. This 
seems to unnecessary complicate applications that may wish to use both 
drafts (such as BLS signatures).
3) Section 4.2.1, p 18: The domain parameters for BLS12_381 seem 
underspecified: while the towering fields construction for GF(p^{12}) 
via GF(p), GF(p^2) = GF(p)[u] / (u^2 + 1),  GF(p^6) = GF(p^2)[v] / (v^3 
- u - 1), and GF(p^{12}):=GF(p^6)[w]/(w^2-v) allows each field elements 
of GF(p^{12}) to be expressed as polynomial in GF(p)[u,v,w], where 
variables are from {1,u}x{1,v,v^2}x{1,w}, this still leaves lots of 
wiggle room in picking u, v, and w (these are not unique, e.g., 
f(u):=u^2+1 has two roots, viz. u and -u:=u^p, etc.). In this particular 
case, this may lead to ambiguity in representation of elements of 
GF(p^{12}) and ambiguity in the Ate pairing result (here, 12 isomorphic 
choices) if these picks are not specified. The same remark applies to 
other domain parameters, such as with BN462 (Section 4.2.2) and 
BLS48_581 (Section 4.3). This may also lead to ambiguity of point 
compression and decompression processes (Appendix C).
4) Section 4.1, p. 13, first para leaves out pairing-friendly curves 
with sub-128-bit security "due to space limitations", but then - 
puzzlingly - adds those back in Appendix D (presumably, since "useful 
information for implementers"). What is the point of including in this 
draft parameter sets that do not make the post-exTNFS cut? This raises a 
more general philiosophical point what the primary purpose of this draft 
is: from Sections 4.2.1, 4.2.2, and 4.3, it seems the main point is to 

define BN462, BLS12_381, and BLS48_581 as suitable pairing-based 
constructs, whereas Table 1, collateral info, and, e.g., the abstract 
suggest more of a survey objective, and lots of company and library 
naming suggests highlighting toolkits and industry players who have put 
a foot into this area over the last 20 years. It would help the reader 
to be more clear about objectives.
5) Section 2.5, p. 9: representation of finite fields is suggested to 
follow conventions in [7], but does not: in [7], finite field elements 
are represented using polynomial construction conventions with 
highest-order index first ordering (see [7], Appendix B), and not a 
towering field construction.

Editorial comments:
1) Section 2.1, p. 6, 1st para: the requirement that the discriminant 
Delta:= 4*a^3+27*b^2 of short-Weierstrass curve W_{a,b} is nonzero holds 
in GF(q) and not in the ring of integers modulo q (these notions are 
different if q:=p^m and m>1).
2) The rev10 draft uses BLS12_381 to refer to the pairing-friendly curve 
that is denoted as BLS12-381 (i.e. differently) in the hash-to-curve 
draft [6].
3) Sections 4.2.1 and 4.2.2 indicate the domain parameters being 
specified in their title, while Section 4.3 (which specifies BLS48_581) 
does not.
4) Section 5 (Security Considerations), p. 26, 2nd para, l. 2: the group 
G_3 (image of pairing map) is commonly called (also elsewhere in the 
draft) G_T.
5) Appendix A, p. 35, 2nd para:  the affine coordinates of Q1 should 
read (x_1, y_1), rather than (x_1, x_2). (Not sure why one needs the 
"underscore" notation instead of simply writing x1, y1, x2, y2, etc.) 
Note: unfortunately, this shows that, even with very small changes from 
the rev-09 to the rev-10 draft, errors can still easily creep in...
6) References, pp. 27-35: the references to the hash-to-curve draft [6] 
(April 13, 2021), the lwig-curve-representations draft [7], and the 
bls-signature draft [8] all need updating (since refer to old drafts); 
almost all normative references seem misclassified (since 
informational); lots of informal references refer to blogs, github 
pages, and company websites (thereby, calling into question longevity, 
stability, and technical nature of content); some references lack 
sufficient detail (e.g., the [ECRYPT] reference is undated; the [NIST] 
leaves out versioning info [supposedly Revision 5]); there seems to be a 
severe case of "reference stuffing", where it is unclear whether this 
supports or hampers the audience of the draft to appreciate its 
message(s). As an aside, the [SG] reference is to IACR ePrint 2018/193 
(instead of 2019/193); the link to BLS12_381 in [ZCashRep] is broken.
7) Acknowledgements, p. 27: I don't think there is a need to categorize 
comments as received from "expert reviewers" and those received from 
others. To my knowledge, CFRG is no caste system and comments received 
from, e.g., Crypto Review panel members, do not carry any more weight 
than those received from others. {This should not need to be stated, if 
disposition of feedback on reviews on previous versions of the draft had 
not included suggestions as if there were such a "pecking order" in place.}

(April 13, 2021)
(June 9, 2021)
(September 10, 2020)

[review posted to CFRG mailing list: Wed Nov 11, 2020, 5.10pm EST (first 
para below posted 8.12pm EST)]
Review of draft-irtf-cfrg-pairing-friendly-curves-08 (Sep 9, 2021)
Reviewer: Rene Struik
Assessment: again, not ready (perhaps, ditch?)
Note: page numbers in this review refer to rev-08

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).

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 

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?

[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 (June 18, 2020)
Reviewer: Rene Struik
Assessment: not ready

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

[1] draft-ietf-lwig-curve-representations-10
[2] R. Lidl, Niederreiter, "Finite Fields", Cambridge University Press, 
...On 2021-08-13 11:38 a.m., Stanislav V. Smyshlyaev wrote:
> Dear CFRG participants,
> This message starts a second RGLC on "Pairing-Friendly Curves" 
> (draft-irtf-cfrg-pairing-friendly-curves-10), that will end on 
> September, 8th.
> See 
> <> 
> for the latest version of the draft.
> We are having the second RGLC since Yumi Sakemi has provided (see 
> <>) 
> updated replies for the questions raised after the first RGLC.
> Please send your comments, as well as expression of support to publish 
> as an RFC (or possible reasons for not doing so) in reply to this 
> message or directly to CFRG chairs.
> Regards,
> Stanislav, Nick and Alexey
> _______________________________________________
> CFRG mailing list

email: | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867