Subject: Re: [Crypto-panel] Request for review: draft-irtf-cfrg-pairing-friendly-curves-03

From: Chloe Martindale <[email-masked]>
Date: Mon, 1 Jun 2020 10:53:31 +0100

Dear Yumi, dear all,

thank you for the update and for involving me in your thought process
regarding the curve choices. I understand and agree with your reasoning
(and approach) regarding including both BLS12-381 and BN462, however I
think I would make a different 'safer choice'.

My reason is this: if the attack is improved further (which you are
completely right, it may), it is very likely to have a bigger impact on
curves constructed via polynomial methods with embedding degree 8 (such as
BN462) than on any other curves for this security level, so it's not
unlikely that the security of BN462 would be pushed below 128 bits. A safer
choice in my view would be to take the Cocks-Pinch curve (not constructed
using polynomial methods) defined using a 544-bit prime implemented in
RELIC, from [GMT19]*. The TNFS attacks cannot be applied to Cocks-Pinch
curves (at least not without a fundamental new attack idea, since they rely
on the polynomial construction), so small improvements will not decrease
the security level at all, and this curve is actually still more efficient
than BN462 so there's nothing to lose there. I appreciate that such a
choice would mean also including some background on Cocks-Pinch and a
reference/short explanation of the fact that TNFS attacks don't apply to
these, which would be a major change to the original document, so I
appreciate it if you'd rather not do this, but just thought I'd suggest it
as I think it would increase the lifetime of your document.

*In your draft this is [GME19], but it should be [GMT19], and can now be
updated to the peer-reviewed version of course (this is the paper I pointed
out in my review).

All the best,
Chloe

On Fri, 29 May 2020 at 16:21, Yumi Sakemi <[email-masked]> wrote:

> Dear Chloe
>
> We appreciate a lot of constructive comments received at Expert Review.
>
> We are currently working on updating our draft.
> Last week, Nick created a repository for pairing-friendly curves on
> CFRG's official GitHub, so we plan to update our draft using the issue
> tracker.
> The updating for your comments will be made available to you on the
> following issue page.
>
> https://github.com/cfrg/draft-irtf-cfrg-pairing-friendly-curves/issues
>
> We will contact you again when all the comments have been updated.
> In that case, we would be glad if you could check them.
>
> In addition, before updating, there is a comment that we would like to
> inform you about the policy of update.
> The comment is about the recommended curve for 128-bit security level.
>
> First of all, thank you for teaching us a peer-reviewed paper for
> BLS12-381.
> The comment is about the recommended curve for 128-bit security level.
> Due to our lack of investigation, we made the wrong decision that
> BLS12-381 was not matched in our selection policy.
>
> Your comment pointed out that BLS12-381 is moved to the recommended
> curve and BN462 is moved to the Appendix.
> We understood the disadvantages of BN462 that you were concerned
> about, but we would like to recommend both BLS12-381 and BN462.
> The reason is as follows.
>
> CFRG aims to standardize cryptographic technology for future Internet use.
> We agree that BLS12-381 with a 126-bit security level is the best
> match as a curve of 128-bit security level "at this time" from the
> viewpoint of security and efficiency.
> On the other hand, the security of BLS12-381 is already less than
> 128bit, so from the viewpoint of future use, if the attack is improved
> even a little, it will not be suitable for a curve of 128-bit security
> level.
> Considering that the curve of 128-bit security level is often used at
> current.
> So, we would like to recommend both BLS12-381 and BN462 considering
> the future use and the safety side.
>
> However, as you pointed out, BN462 has the disadvantage of being too
> slow compared to BLS12-381.
> Then, the reader will be confused if there are two parameters of
> 128-bit security level, so we will add the basis for selection by
> adding the explanation of merits and demerits for each parameter.
> And, we will also add a description about the disadvantages of BN462
> regarding efficiency.
>
> If you have any problems with the updating policy, we would like you to
> comment.
>
> Best regards,
> Yumi
>
>
>
>
>
>
> 2020年4月27日(月) 21:58 Yumi Sakemi <[email-masked]>:
> >
> > Dear Chloe
> >
> > I appreciate your review.
> > I'm very glad to receive many constructive comments!
> > I will discuss about your comments with co-authors and revise our
> > draft to reflect your comments in our draft.
> > I think it will be a better draft by reflecting your comments.
> >
> > As co-author Tsunekazu e-mailed, we're  planning to submit version 04,
> > because we were independently working on updating of abstract,
> > introduction (sec. 1.3) and proofreading of English in parallel with
> > the expert review.
> > (Version 04 will not be reflected your comments.)
> >
> > Comments from Chloe will be reflected in the version 05.
> > We will submit version 05 in mid-May and we will report you when we
> > submit version 05.
> >
> > Dear Stanislav
> >
> > Thank you very much for proceeding to the Expert review.
> > We received a lot of constructive comments from Chloe, so I think it
> > is difficult to manage comments by email.
> > (Because there are over 100 comments from Chloe.)
> >
> > Therefore, I would like to use the issue management function of GitHub
> > so that it is easy to check the reflecting status of Chloe's comments.
> > So, I'd like to use the repository of pairing-friendly curves draft on
> > CFRG's GitHub
> > because BLS signature which is similar in terms of IRTF stream is also
> > registered on the GitHub.
> > Could you register the repository for the draft of pairing-friendly
> > curves on the following CFRG's GitHub?
> >
> > https://github.com/cfrg
> >
> > Best regards,
> > Yumi
> >
> > 2020年4月27日(月) 10:09 SAITO Tsunekazu <[email-masked]>:
> > >
> > > Dear Chloe, Stanislav,
> > >
> > >
> > >
> > > This is Tsunekazu.
> > >
> > >
> > >
> > > We plan to update the draft to version 04 soon.
> > >
> > > As the contents of the update, we changed the wording of Section 1.3
> and security consideration.
> > >
> > > Yumi will submit the 4th edition, so please wait a moment.
> > >
> > >
> > >
> > > Best regards,
> > >
> > > Tsunekazu
> > >
> > >
> > >
> > > From: Stanislav V. Smyshlyaev <[email-masked]>
> > > Sent: Sunday, April 26, 2020 2:30 PM
> > > To: Chloe Martindale <[email-masked]>; SAITO Tsunekazu <
> [email-masked]>; Tetsutaro Kobayashi <
> [email-masked]>; Yumi Sakemi <
> [email-masked]>
> > > Cc: [email-masked]; [email-masked]
> > > Subject: Re: [Crypto-panel] Request for review:
> draft-irtf-cfrg-pairing-friendly-curves-03
> > >
> > >
> > >
> > > Dear Chloe,
> > >
> > > Many thanks for your review (such a great and a prompt one!).
> > >
> > >
> > >
> > > Dear Yumi, Saito, Tetsutaro, do you plan to update your draft taking
> into account Chloe’s review?
> > >
> > >
> > >
> > > Best regards,
> > >
> > > Stanislav
> > >
> > >
> > >
> > > пт, 24 апр. 2020 г. в 19:49, Chloe Martindale <
> [email-masked]>:
> > >
> > > Hi all,
> > >
> > >
> > >
> > > review is attached.
> > >
> > >
> > >
> > > All the best,
> > >
> > > Chloe
> > >
> > >
> > >
> > > On Tue, 21 Apr 2020 at 18:05, Stanislav V. Smyshlyaev <
> [email-masked]> wrote:
> > >
> > > Sure - it is
> > >
> > > https://tools.ietf.org/html/draft-irtf-cfrg-pairing-friendly-curves-03
> > >
> > >
> > >
> > > Thank you again!
> > >
> > >
> > >
> > > Regards,
> > >
> > > Stanislav
> > >
> > >
> > >
> > > вт, 21 апр. 2020 г. в 19:10, Chloe Martindale <
> [email-masked]>:
> > >
> > > Just to be sure, can you point me towards the most recent version of
> the draft please?
> > >
> > >
> > >
> > > Thanks,
> > >
> > > Chloe
> > >
> > >
> > >
> > > On Tue, 21 Apr 2020 at 13:17, Stanislav V. Smyshlyaev <
> [email-masked]> wrote:
> > >
> > > Great, many thanks, Chloe!
> > >
> > >
> > >
> > > Kind regards,
> > >
> > > Nick, Alexey, Stanislav
> > >
> > >
> > >
> > > On Tue, 21 Apr 2020 at 15:16, Chloe Martindale <
> [email-masked]> wrote:
> > >
> > > I'll take a look this week.
> > >
> > >
> > >
> > > All the best,
> > >
> > > Chloe
> > >
> > >
> > >
> > > On Tue, 21 Apr 2020, 13:10 Stanislav V. Smyshlyaev, <[email-masked]>
> wrote:
> > >
> > > Dear Crypto Panel members,
> > >
> > >
> > >
> > > The authors of the Pairing-Friendly Curves draft have addressed the
> concerns raised during the discussion and are ready to move to the next
> stage with the draft.
> > >
> > >
> > >
> > > Alexey, Nick and I would like to ask Crypto Review Panel members about
> the review(s) of draft-irtf-cfrg-pairing-friendly-curves-03.
> > >
> > >
> > >
> > > This memo introduces pairing-friendly curves used for constructing
> pairing-based cryptography. It describes recommended parameters for each
> security level and recent implementations of pairing-friendly curves.
> > >
> > >
> > >
> > >
> > >
> > > Can we have any volunteers, please?..
> > >
> > >
> > >
> > >
> > >
> > > Best regards,
> > >
> > > Stanislav (on behalf of chairs)
> > >
> > > _______________________________________________
> > > Crypto-panel mailing list
> > > [email-masked]
> > > https://www.irtf.org/mailman/listinfo/crypto-panel
> >
> >
> >
> > --
> > Yumi Sakemi, Ph. D.
> > Lepidum Co. Ltd.
> > E-Mail: [email-masked]
>
>
>
> --
> Yumi Sakemi, Ph. D.
> Lepidum Co. Ltd.
>
> Tel: +81-3 6276 5103
> E-Mail: [email-masked]
>

---

From: Yumi Sakemi <[email-masked]>
Date: Tue, 9 Jun 2020 20:02:30 +0900

Dear Chloe

Thank you for your e-mail.

We are very glad to reach a rough consensus with you.
We believe that our draft became very readable and higher quality by
reflecting your comments.
We appreciate your valuable and constructive comments.

We'd like to express our gratitude and include your name in Acknowledgement.
The version 05 that is reflected your comments will be submitted today
or tomorrow, then we will contact you again.

Best regards,
Yumi

2020年6月1日(月) 18:53 Chloe Martindale <[email-masked]>:
>
> Dear Yumi, dear all,
>
> thank you for the update and for involving me in your thought process regarding the curve choices. I understand and agree with your reasoning (and approach) regarding including both BLS12-381 and BN462, however I think I would make a different 'safer choice'.
>
> My reason is this: if the attack is improved further (which you are completely right, it may), it is very likely to have a bigger impact on curves constructed via polynomial methods with embedding degree 8 (such as BN462) than on any other curves for this security level, so it's not unlikely that the security of BN462 would be pushed below 128 bits. A safer choice in my view would be to take the Cocks-Pinch curve (not constructed using polynomial methods) defined using a 544-bit prime implemented in RELIC, from [GMT19]*. The TNFS attacks cannot be applied to Cocks-Pinch curves (at least not without a fundamental new attack idea, since they rely on the polynomial construction), so small improvements will not decrease the security level at all, and this curve is actually still more efficient than BN462 so there's nothing to lose there. I appreciate that such a choice would mean also including some background on Cocks-Pinch and a reference/short explanation of the fact that TNFS attacks don't apply to these, which would be a major change to the original document, so I appreciate it if you'd rather not do this, but just thought I'd suggest it as I think it would increase the lifetime of your document.
>
> *In your draft this is [GME19], but it should be [GMT19], and can now be updated to the peer-reviewed version of course (this is the paper I pointed out in my review).
>
> All the best,
> Chloe
>
>> First of all, thank you for teaching us a peer-reviewed paper for BLS12-381.
>> Considering that the curve of 128-bit security level is often used at current.
>> If you have any problems with the updating policy, we would like you to comment.
>>
>> Best regards,
>> Yumi
>>
>>
>>
>>
>>
>>
>> > > As the contents of the update, we changed the wording of Section 1.3 and security consideration.
>> > >
>> > > To: Chloe Martindale <[email-masked]>; SAITO Tsunekazu <[email-masked]>; Tetsutaro Kobayashi <[email-masked]>; Yumi Sakemi <[email-masked]>
>> > > Subject: Re: [Crypto-panel] Request for review: draft-irtf-cfrg-pairing-friendly-curves-03
>> > >
>> > >
>> > >
>> > > Dear Chloe,
>> > >
>> > > Dear Yumi, Saito, Tetsutaro, do you plan to update your draft taking into account Chloe’s review?
>> > >
>> > >
>> > >
>> > > Best regards,
>> > >
>> > > Stanislav
>> > >
>> > >
>> > >
>> > > пт, 24 апр. 2020 г. в 19:49, Chloe Martindale <[email-masked]>:
>> > >
>> > > Hi all,
>> > >
>> > >
>> > >
>> > > review is attached.
>> > >
>> > >
>> > >
>> > > All the best,
>> > >
>> > > Chloe
>> > >
>> > >
>> > >
>> > > On Tue, 21 Apr 2020 at 18:05, Stanislav V. Smyshlyaev <[email-masked]> wrote:
>> > >
>> > > Sure - it is
>> > >
>> > > вт, 21 апр. 2020 г. в 19:10, Chloe Martindale <[email-masked]>:
>> > >
>> > > Just to be sure, can you point me towards the most recent version of the draft please?
>> > >
>> > >
>> > >
>> > > Thanks,
>> > >
>> > > Chloe
>> > >
>> > >
>> > >
>> > > On Tue, 21 Apr 2020 at 13:17, Stanislav V. Smyshlyaev <[email-masked]> wrote:
>> > >
>> > > On Tue, 21 Apr 2020 at 15:16, Chloe Martindale <[email-masked]> wrote:
>> > >
>> > > On Tue, 21 Apr 2020, 13:10 Stanislav V. Smyshlyaev, <[email-masked]> wrote:
>> > >
>> > > The authors of the Pairing-Friendly Curves draft have addressed the concerns raised during the discussion and are ready to move to the next stage with the draft.
>> > >
>> > >
>> > >
>> > > Alexey, Nick and I would like to ask Crypto Review Panel members about the review(s) of draft-irtf-cfrg-pairing-friendly-curves-03.
>> > >
>> > >
>> > >
>> > > This memo introduces pairing-friendly curves used for constructing pairing-based cryptography. It describes recommended parameters for each security level and recent implementations of pairing-friendly curves.
>> > >
>> > >
>> > >
>> > >
>> > >

-- 
Yumi Sakemi
Lepidum Co. Ltd.

---

From: Yumi Sakemi <[email-masked]>
Date: Wed, 10 Jun 2020 13:06:20 +0900

Dear Alexey, Nick, Stanislav, and Chloe

We have submitted the latest version 05 of the draft "Pairing-Friendly Curves".
https://datatracker.ietf.org/doc/draft-irtf-cfrg-pairing-friendly-curves/

We have categorized a lot of comments received in the Expert Review
into more than 40 issues, and reflected the results which we
considered all of issues to the latest version.
While we revised the draft, we received comments from other CFRG
members and the authors of the draft "BLS Signatures", and reflected
them to the latest version.

If you want to know the details of how to revise, you can check them
by closed issues on the official CFRG GitHub page.

https://github.com/cfrg/draft-irtf-cfrg-pairing-friendly-curves/issues?q=is%3Aissue+is%3Aclosed

Thanks to valuable and constructive comments from Chloe and CFRG
members, our draft became readable and higher quality.
We strongly believe that the draft is ready for RG Last Call.
If there are other necessary procedures for RGLC, could you tell us?

Best regards,
Yumi

-- 
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.

---

From: Chloe Martindale <[email-masked]>
Date: Mon, 15 Jun 2020 17:28:33 +0100

Dear Yumi, dear all,

thank you for carefully taking my comments into consideration. I am much
happier with the draft now! There are a few typos left, see below, and I
just had a couple of comments on the security discussion but these are
easily fixed. If you fix these small things in my opinion it's ready for RG
Last Call.

Abstract:
Pairing is a special map -> Pairings are special maps OR A pairing is a
special map

1.1
'Pairing is a special map' -> 'Pairings are special maps OR A pairing is a
special map'
'importance of pairing' -> 'importance of pairings'
'pairing is efficiently computable' -> 'pairings are efficiently
computable'.

1.2
pairins -> pairings

1.3
(NSF) -> (NFS)
Barbulescu et. al. -> Barbulescu and Duquesne. (Authors are alphabetical).

2.2
-'The optimal Ate pairing is considered to be the most efficient to compute
is the one that is most commonly used for practical implementation.' ->
'The optimal Ate pairing is considered to be the most efficient to compute
and is the one that is most commonly used for practical implementation.'
-Choose G_2 or G2 (probably G_2 is easier since there are many instances
also of G_1 and G_T)
-'There also exists cyclic subgroup' -> 'There also exists a cyclic
subgroup'

2.3
-'b is an element of multiplicative group of order p' -> 'b is a nonzero
element of F_p' OR 'b is an element of a multiplicative group (F_p)^* of
order p-1' OR 'b is an element of the multiplicative group of F_p'
-'embedded degree' -> 'embeddiing degree'

2.4
-'r-torsions' -> 'r-torsion'

2.5
-(paragraph 2): of degree d' -> of degree d

4.2
-This sentence has slightly weird grammar so I don't fully understand what
you want to say: 'Therefore, the curve of the 128-bit security level
   is often used at current, so this memo recommends both BLS12-381 and
   BN462 in consideration of the future use and the safety side.'
Do you mean:
'As curves of 128-bit security level are currently the most widely used, we
recommend both BLS12-381 and BN462 in this memo in order to have a more
efficient and a more prudent option respectively.'

4.2.1
-This comment is maybe a bit misleading:
'We have to note that, according to [BD18], the bit length of p for
   BLS12 to achieve 128-bit security is calculated as 461 bits and more,
   which BLS12_381 does not satisfy.'
The 461-bit figure in [BD18] is based on a rough estimate which varies a
lot between different examples (as is necessary when giving a broad
overview). The exact complexity of [BD18]'s attack depends on the specific
polynomial used to construct the family and can change the complexity of
the attack by up to about 12 bits. The proposed construction of BLS12_381
you refer to here has been specially chosen to minimize the impact of the
exTNFS attack. It would in my opinion be more precise to say:
'We have to note that the security level of this pairing is expected to be
126 rather than 128 bits [GMT19]'.

4.2.2
-This comment could be more clearly worded:
'We have to note that the BN462 becomes slower compared to BLS12_381,
   although the BN462 is suitable for the parameters of the 128-bit
   security level for the use of the future internet.'
How about instead:
'We have to note that BN462 is significantly slower than BLS12_381,
   but has 134-bit security level [GMT19],
   so may be more resistant to future small improvements to the exTNFS
attack.'

This would be a good place to also add a remark along the lines of:
'We note also that CP8_544 is more efficient than BN462, has 131-bit
security level,
and that due to its construction will not be affected by future small
improvements to the exTNFS attack. However, as this curve is not widely
used (it is only implemented in one library), we instead chose BN462 for
our 'safe' option.'

5.
-'BLS curves of embedding degree 12 require' -> 'BLS curves of embedding
degree typically require' (cf. my comment on 4.2.1)

All the best,
Chloe

On Wed, 10 Jun 2020 at 05:06, Yumi Sakemi <[email-masked]> wrote:

> > > *In your draft this is [GME19], but it should be [GMT19], and can now
> be updated to the peer-reviewed version of course (this is the paper I
> pointed out in my review).
> > >
> > > All the best,
> > > Chloe
> > >
> > >> > > To: Chloe Martindale <[email-masked]>; SAITO
> Tsunekazu <[email-masked]>; Tetsutaro Kobayashi <
> > >> > > The authors of the Pairing-Friendly Curves draft have addressed
> the concerns raised during the discussion and are ready to move to the next
> stage with the draft.
> > >> > >
> > >> > >
> > >> > >
> > >> > > Alexey, Nick and I would like to ask Crypto Review Panel members
> about the review(s) of draft-irtf-cfrg-pairing-friendly-curves-03.
> > >> > >
> > >> > >
> > >> > >
> > >> > > This memo introduces pairing-friendly curves used for
> constructing pairing-based cryptography. It describes recommended
> parameters for each security level and recent implementations of
> pairing-friendly curves.
> > >> > >
> > >> > >
> > >> > >
> > >> > >
> > >> > >

---

From: Yumi Sakemi <[email-masked]>
Date: Tue, 16 Jun 2020 16:09:30 +0900

Dear Chloe, Alexey, Nick, and Stanislav

We are very grateful to you for your useful comments.
We submitted the version 06 of the draft "Pairing-Friendly Curves".

We have categorized your comments into 7 issues and reflected the
content of all issues in the version 06.
These correspond to issues #49 to #55.
You can check how to modify on the following GitHub page.

Dear CFRG chairs

We believe that we were able to complete the remaining issues up to RG
Last Call, which we received from Chloe.
Could you please consider starting RG Last Call?

Best regards,
Yumi

2020年6月16日(火) 1:28 Chloe Martindale <[email-masked]>:
>
> Dear Yumi, dear all,
>
> thank you for carefully taking my comments into consideration. I am much happier with the draft now! There are a few typos left, see below, and I just had a couple of comments on the security discussion but these are easily fixed. If you fix these small things in my opinion it's ready for RG Last Call.
>
>
>
> Abstract:
> Pairing is a special map -> Pairings are special maps OR A pairing is a special map
>
> 1.1
> 'Pairing is a special map' -> 'Pairings are special maps OR A pairing is a special map'
> 'pairing is efficiently computable' -> 'pairings are efficiently computable'.
>
> 1.2
> pairins -> pairings
>
> 1.3
> (NSF) -> (NFS)
> -'The optimal Ate pairing is considered to be the most efficient to compute is the one that is most commonly used for practical implementation.' -> 'The optimal Ate pairing is considered to be the most efficient to compute and is the one that is most commonly used for practical implementation.'
> -Choose G_2 or G2 (probably G_2 is easier since there are many instances also of G_1 and G_T)
> -'There also exists cyclic subgroup' -> 'There also exists a cyclic subgroup'
>
> 2.3
> -'b is an element of multiplicative group of order p' -> 'b is a nonzero element of F_p' OR 'b is an element of a multiplicative group (F_p)^* of order p-1' OR 'b is an element of the multiplicative group of F_p'
> -This sentence has slightly weird grammar so I don't fully understand what you want to say: 'Therefore, the curve of the 128-bit security level
> 'As curves of 128-bit security level are currently the most widely used, we recommend both BLS12-381 and BN462 in this memo in order to have a more efficient and a more prudent option respectively.'
>
> 4.2.1
> The 461-bit figure in [BD18] is based on a rough estimate which varies a lot between different examples (as is necessary when giving a broad overview). The exact complexity of [BD18]'s attack depends on the specific polynomial used to construct the family and can change the complexity of the attack by up to about 12 bits. The proposed construction of BLS12_381 you refer to here has been specially chosen to minimize the impact of the exTNFS attack. It would in my opinion be more precise to say:
> 'We have to note that the security level of this pairing is expected to be 126 rather than 128 bits [GMT19]'.
>
> 4.2.2
>    so may be more resistant to future small improvements to the exTNFS attack.'
>
> 'We note also that CP8_544 is more efficient than BN462, has 131-bit security level,
> and that due to its construction will not be affected by future small improvements to the exTNFS attack. However, as this curve is not widely used (it is only implemented in one library), we instead chose BN462 for our 'safe' option.'
>
> 5.
> -'BLS curves of embedding degree 12 require' -> 'BLS curves of embedding degree typically require' (cf. my comment on 4.2.1)
>
> All the best,
> Chloe
>
>

-- 
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.