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

[Yumi Sakemi <[e-mail]>]

Dear CFRG members

I sent an email to the CFRG ML, but I got an error message, so I forward it.

Best regards,
Yumi

---------- Forwarded message ---------
From: Yumi Sakemi <[e-mail]>
Date: 2021年5月1日(土) 5:47
Subject: Re: [CFRG] Second RGLC on draft-irtf-cfrg-pairing-friendly-curves
To: Rene Struik <[e-mail]>
Cc: CFRG <[e-mail]>, SAITO Tsunekazu
<[e-mail]>, Tetsutaro Kobayashi
<[e-mail]>, <[e-mail]>


Dear Rene

Thank you for your e-mail.
I am very sorry for the delay in responding to your email at the start
of the 2nd RGLC.

I had already responded to the main part of your comment in November
2020 in the following email I sent in December 2020, and we were
waiting for your response to that communication.
https://mailarchive.ietf.org/arch/msg/cfrg/2i183zl28y4fK54oIwqEfEVVu0U/


I was relieved to hear from you, as I had been worried that I had not
heard from you for a long time.

Since there is a possibility that you may not have read my e-mail in
December, I will reply to each of your comments again in this e-mail.
I apologize for the length of this message in advance.


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

Thank you for your comments.
As you may know, many of the drafts registered on CFRG use GitHub's
issue feature to track revisions and changes of drafts.
You can refer to the following URL.
https://github.com/cfrg

So, let me add that this is not our original management method.
In addition, for comments that were not reflected as a result of
discussions among the authors, the reasons for not reflecting them are
also listed.
Could you please check again our reply comments for your comments if
you have any additional concerns?


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

I'm sorry that the purpose of our draft was difficult to understand.
Let me explain the target of standardization again.
Our goal is to standardize secure parameters for pairing-based
cryptographic applications.
Since the 2016 Kim's attack made widely used standard parameters no
longer secure enough, we are organizing existing parameters and, among
others, showing which parameters should be used for each bit security.

As reference information, the calculation method of pairing is
described, but it is out of the scope of standardization
And also, an educational purpose for pairing is out of the scope of our draft.

On the other hand, in response to your comment, the authors have
discussed why this misunderstanding has occurred and thought that the
current title may be too generic and inappropriate.

The current title is "Pairing-Friendly Curves", which may have given
the impression of a broad standardization of information about
pairing.
We thought it would be a better idea to change the title to something
more specific to secure parameters of pairing, such as "Secure
Parameters of Pairing-Friendly Curves".
Would this address the misconceptions and concerns underlying your comment?

Also, the reason why we are describing the implementation status is
that in standardizing the parameters it is because this information is
essential to show how the parameters were selected.
There is no purpose to advertise the company or implementer.


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

I think this comment is corresponds to Detailed Comments, so I'll
provide detailed answers there.
As you know because you commented in detail, our target is a specific
pairing calculation called "Optimal Ate pairing", not Ate pairing.
Optimal Ate pairing is an improved version of Ate pairing proposed by
F. Vercauteren in 2008.

F. Vercauteren, "Optimal Pairings",
available at https://eprint.iacr.org/2008/096.pdf, 2008.


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

Thank you for your comments.
We believe that there is no problem to proceed with standardization in
CFRG because we are following the IETF manner.
In light of the situation in our draft, we recognize that there is no
change in the situation that would overturn the approval in the
Adoption Call.
Regarding the table on implementation status, other CFRG members
pointed out the size of the table.
For this, I followed your comments and increased readability by
splitting the table.
Also, this table is required information to show that we are following
the selection policy, not to advertise it.
We are aware that we have reached a consensus by keeping the size to
the minimum required.


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

Thank you for pointing this out.
I understood that your comment means that in Appendix A, the
expressions for the x- and y-coordinates in the Affine coordinates of
the rational point A are represented as A[1] and A[2], respectively.
I agree with your point that the expressions are not familiar, so I
will correct it by using the symbols x and y.


>2) Appendix A, last para before A.1: one should mentions the image of
>the point-at-infinity under this Frobenius map.

I am afraid that I explain this to experts, but the Frobenius map is
an isomorphism map, so the identity element (the point at infinity) is
mapped to the identity element.
Since we think it is trivial, we describe no explanation about it.

>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);
The parameter t is defined in the main part of 4.2.1 and 4.2.2, so I
hope you will check the draft properly.
Also, the method of expressing parameters p and r as polynomials of
the basic parameters (in this case t) is familiar to those in the
field of pairing.


>(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;
Thank you for your comments.
As a reiteration, we would like to note that our target is *Optimal*
Ate pairing.
As mentioned in the draft, the parameter c is a specific value
determined by the parameter t.
The calculation method is outside the scope of our standardization,
and since there are several ways to expand c, our policy is that
implementers can choose the best one.


>(c) fix the loop to "for i:=L-1 downto 0";
Thanks for pointing that out.
I'll revise it to "downto" according to your comments.

>(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);

Thank you for your comments.
Indeed, I agree that it is not common to express "or" with "|".
So, I will define "! =" is defined as "not equal to" in advance and
then modify to "c_i ! = zero".


>(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?;
I'm sorry but I had a typo, so thank you for pointing it out.
I will revise it.

>(e) how does one know the line function never receives
>non-affine points as input?;

You can also calculate pairing with other coordinates than Affine
coordinates, such as projective coordinates.
However, we have a policy of not mentioning specific calculations that
use other coordinates in particular, as it may violate patents.
We recognize that there is no big influence even if the coordinates
are different because it does not affect the final calculation results
of pairing or test vectors.


>(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)?
Algorithms using the Frobenius map are not the target of our standardization.
For this reason, we consider the reference information on the
calculation method to be sufficient.
If you want to know the details of the calculation method, please
refer to the reference information.



>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)*)?

We believe that it is clear from the method of calculation that f does
not equal zero.
For f to be zero, the numerator of the Line Function needs to be zero.
The numerator of the Line Function is when the difference of the
x-coordinates of the points is zero, that is, in an elliptic curve,
when the two input rational points are equal.
However, in this case, the process is (3 * A[1]^2), which is not zero.
Implementers can check that the implementation is correct by testing
with test vectors and boundary values.


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

Although the NAF representation is sometimes used as a side-channel
countermeasure, the NAF representation in pairing calculations is used
for accelerating purposes.
The reason for this is that the parameter c is public information, not secret.
The cases where side-channel attack countermeasures are required as
pairing-based cryptography are described in security considerations.


>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.
Thank you for pointing this out.
We will revise the description so that description is aligned.


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

We consider it sufficient to show that pairing realizes for great
applications in the Introduction section.


>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.
Thanks for your comments.
The symbol e consistently represents the value of the pairing in the
draft, but we will describe the explanation again.


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

I recognized that detailed comments 9 and 10 are about Appendix C.
The position of Appendix C is that it is reference information for
implementers, not a standardization target.
Since the author understands that the methods in Appendix C don't
apply to BN462, it is also clearly stated that the methods are for
BLS12-381 and are for reference only.
As for the contents of the Appendix in the draft (excluding typos), I
think that there is no problem with the current expression.


>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.
Thank you for your comment.
This is not a technique specific to BN curves, so we will remove "for
BN curves".

>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?
Thank you for your suggestion.
We will revise it according to your comments.


>3) Appendix B, l. 8: in "where u is a indeterminate", change "a" to "an".
I’m sorry but I had a typo, so thank you for pointing it out.
I will revise it.

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

Thanks for pointing this out.
I will revise the wording to be consistent, using underscores.
Additionally, we will revise the title as you suggested.

>5) Appendix C, p. 49: replace "sign_F_p" by "sign_GF(p)", etc.
Thank you for your comments.
I will revise it.

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

There is no cross-marketing implication as you have pointed out.
As for the pairing draft, we are citing it because it is a draft that
should be cited from the perspective that the Hashing feature is
necessary for the protocol implementation.

Best regards,
Yumi

2021年3月18日(木) 21:53 Rene Struik <[e-mail]>:
>
> Hi Stanislav:
>
> I am puzzled that the 2nd WGLC is on rev09 of the pairing curve draft (i.e., the one posted on Nov 16th last year).
>
> On Nov 11th, I posted another review on rev08 of this document (see [1]) {for my review of the previous rev07 version, see [2]}.
>
> I could not find any response by the authors to my detailed comments of my rev08 review. Since they posted the current rev09 version (that is under 2nd WGLC) on Nov 16th, considerations of those comments must have happened within that 5-day time window. The authors, however, stated in [3]  "Because we are currently considering Rene's latest comments, I'm sorry but this version does not reflect them".
>
> Isn't the normal step to consider received comments? If so, isn't the 2nd WGLC premature?
>
> (FYI - the authors only commented - after almost four months - on my minor note regarding normative vs. informative reference classification, but not at all on the much larger review I did in [1].)
>
> Best regards, Rene
>
> [1] Review RS of draft-irtf-cfrg-pairing-friendly-curves-08 (Nov 11, 2020):
> https://mailarchive.ietf.org/arch/msg/cfrg/kAQwgiKejMby4aYONkQzt0ZiOOU/
>
> [2] Review RS of draft-irtf-cfrg-pairing-friendly-curves-07 (July 12, 2020):
> https://mailarchive.ietf.org/arch/msg/cfrg/pW71h3yUETnqedHsH0m3rwzPnm4/
>
> [2] Message Yumi Sakemi on draft-irtf-cfrg-pairing-friendly-curves-09 (Nov 16, 2020):
> https://mailarchive.ietf.org/arch/msg/cfrg/NNpHIWGOvsSBd22gg7Ve10zDhT4/
>
>
> On 2021-03-18 7:04 a.m., Stanislav V. Smyshlyaev wrote:
>
> Dear CFRG participants,
>
> This message starts a second 3-week RGLC on "Pairing-Friendly Curves" (draft-irtf-cfrg-pairing-friendly-curves-09), that will end on April 9th. See https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/ for the latest version of the draft.
>
> We are having the second RGLC since Yumi Sakemi has provided (see https://mailarchive.ietf.org/arch/msg/cfrg/2-LVS6EXc4TfY1zlHRGUXe3cu6w/) 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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>
>
> --
> email: [e-mail] | Skype: rstruik
> cell: [phone] | US: [phone]
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
Yumi Sakemi, Ph. D.
 Infours Inc.

E-Mail: [e-mail]