Subject: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

From: "Paterson Kenneth" <[email-masked]>
Date: Fri, 6 Sep 2019 11:36:39 +0000

Dear CFRG,

This email commences a 2-week call for adoption for draft-yonezawa-pairing-friendly-curves:

https://datatracker.ietf.org/doc/draft-yonezawa-pairing-friendly-curves/

Please give your views on whether this document should be adopted as a CFRG draft, and if so, whether you'd be willing to help work on it/review it.

Thanks,

Kenny (for the chairs)

---

From: Kobi Gurkan <[email-masked]>
Date: Fri, 6 Sep 2019 14:50:11 +0300

Hi,

Seems like a good idea to have recommendations for pairing friendly curves
for a variety of use-cases.

I want to suggest describing additional topics:
1. Products of pairings/multi-pairings - Many implementations of
pairing-based protocols use these optimizations, so maybe it's worth
discussing the way to do it.
2. More curves being used in the wild - BLS12-377 and SW6 (Cocks-Pinch
curve whose order is the BLS12-377 base field) described in Zexe and used
in Celo, MNT4753/MNT6753 cycle of curves used in Coda.

Kobi

On Fri, Sep 6, 2019 at 2:37 PM Paterson Kenneth <[email-masked]>
wrote:

> Please give your views on whether this document should be adopted as a
> CFRG draft, and if so, whether you'd be willing to help work on it/review
> it.
>
> Thanks,
>
> Kenny (for the chairs)
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Rene Struik <[email-masked]>
Date: Fri, 6 Sep 2019 09:51:33 -0400

Dear colleagues:

I am neutral with respect to adoption of this draft.

I do have an organizational remark regarding CFRG work items, though: if 
this draft is adopted by the CFRG as a working group document, I would 
suggest moving the description of the curves isogenous to BLS-12-381 as 
described in Appendix C of draft-irtf-cfrg-hash-to-curve-04 to the 
pairing curve document, so as to keep the curve mapping document clean 
and keep all core pairing-related stuff in one document.

Section 2.5:
a) s = s_0 + s_1 * p + ... + s_{d - 1} * i^{d - 1} should read s = s_0 + 
s_1 * i + ... + s_{d - 1} * i^{d - 1}, since it is a polynomial in 
indeterminate i.
b) Is there a a reason to represent this as s = s_0 + s_1 * p + ... + 
s_{d - 1} * p^{d - 1}, in lowest-coefficient-first order, rather than in 
highest-coefficient-first order? Why not represent this as 
right-concatenation of the representation of the polynomial coefficients 
s_0, ..., s_{d-1} in GF(p) instead, so each of these can be easily 
extracted individually?
c) The IEEE 1363a-2004 specification referenced is not publicly 
available (well, without paying ~ $100).

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Michael Scott <[email-masked]>
Date: Fri, 6 Sep 2019 17:51:33 +0100

Hello All,

I recommend this draft for adoption. An implementation of proposed curves
is available here - https://github.com/miracl/core

Happy to help and review..

Mike

---

From: Marek Jankowski <[email-masked]>
Date: Sun, 8 Sep 2019 15:18:35 +0200

Hello all,

I support the adoption of this draft and am happy to help work on it or
review it.

Regards,
Marek.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Sun, 8 Sep 2019 22:04:47 -0700

Paterson  Kenneth <[email-masked]> wrote:
> Please give your views on whether this document should be adopted
> as a CFRG draft, and if so, whether you'd be willing to help work
> on it/review it.

I support adoption of this draft, and I'm happy to help review it
and to make sure it's well synchronized with the hash-to-curve and
BLS signatures efforts (just as Armando has already said).

But I am a bit wary about mission creep. In particular I think we
should want pretty strong justification before adding specialized
constructions like the ZEXE curves and the Coda cycle. I'd prefer
for those to live in their own document(s) since probably they're
unnecessary (and add needless cost) for most applications.

-=rsw

---

From: Kobi Gurkan <[email-masked]>
Date: Wed, 11 Sep 2019 13:46:30 +0300

Riad makes a good point. Maybe a SNARK-specific draft could be a better
place.

---

From: SAITO Tsunekazu <[email-masked]>
Date: Thu, 19 Sep 2019 19:57:12 +0900

Dear Rene

This is SAITO Tsunekazu. I am the co-author of draft-yonezawa.

Thank you for your comments about data conversion in Section 2.5.
We will be careful to correct the typo etc. in the next draft. 

(1) Description of Data Conversion
Riad also asked us if we need to describe data conversion.
At that time, Shoko responded that we were considering just a mathematical parameter range as the draft range.
Certainly, if it is necessary to describe the data conversion for implementation, we can describe it separately in the appendix as follows.
https://info.isl.ntt.co.jp/crypt/psec/dl/iso/psec-kem_v2.2_20080414e.pdf

(2) Data Conversion Between Extension Field Element and Octet String.
There are two main methods for this conversion as you said.

(A) a method to assign the characteristic to an indeterminate.
For extension field element as polynomial x = s_0 + s_1 * u + ... + s_{n-1} *u^{n-1}, one assign the prime and compute an integer
int(x) = s_0 + s_1 * p + ... + s_{n-1} *p^{n-1}.
Then we convert to octet string. 

Advantages of this method are
* Adopted by other standards like IEEE and ANSI to ensure consistency.
* You only need to check if the element of the finite field is correct when converted to an integer.

(B) a method of concatenation of each coefficient.
For extension field element as polynomial x = s_0 + s_1 * u + ... + s_{n-1} *u^{n-1}, one concatenate each coefficient s_i oct (x) = s_0 ||s_1|| ... ||s_{n-1}. 

Advantages of this method are
* Fast implementation.
* Easy to implement. 

We understand that there are good points to either method, so we briefly described the conversion method of (A) according to different standards and historical backgrounds. 

Best Regards,
SAITO Tsunekazu

-----Original Message-----
From: Rene Struik <[email-masked]> 
Sent: Friday, September 6, 2019 10:52 PM
To: Paterson Kenneth <[email-masked]>; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

Dear colleagues:

I do have an organizational remark regarding CFRG work items, though: if this draft is adopted by the CFRG as a working group document, I would suggest moving the description of the curves isogenous to BLS-12-381 as described in Appendix C of draft-irtf-cfrg-hash-to-curve-04 to the pairing curve document, so as to keep the curve mapping document clean and keep all core pairing-related stuff in one document.

Section 2.5:
a) s = s_0 + s_1 * p + ... + s_{d - 1} * i^{d - 1} should read s = s_0 +
s_1 * i + ... + s_{d - 1} * i^{d - 1}, since it is a polynomial in indeterminate i.
b) Is there a a reason to represent this as s = s_0 + s_1 * p + ... + s_{d - 1} * p^{d - 1}, in lowest-coefficient-first order, rather than in highest-coefficient-first order? Why not represent this as right-concatenation of the representation of the polynomial coefficients s_0, ..., s_{d-1} in GF(p) instead, so each of these can be easily extracted individually?
c) The IEEE 1363a-2004 specification referenced is not publicly available (well, without paying ~ $100).

Best regards, Rene

---

From: SAITO Tsunekazu <[email-masked]>
Date: Thu, 19 Sep 2019 20:02:57 +0900

Dear Kobi.

This is SAITO Tsunekazu.

Thank you for your comments.

There are two discussions on optimization:
(A) Optimization of curve parameters according to protocol.
(B) Optimization of calculation method with fixed curve parameters.

Regarding (A), I think that it is better to describe the pairing curve with the requirements of some protocols and the parameters that are specific to the calculation.
For example, The curve BLS12-381 is made specifically for the calculation of G3. 
And in the case of BLS signature, the multiplication of G3 needs to be fast in order to composition the signature value. 

On the other hand, The curve BLS48 is made so that the pairing calculation itself is fast. 
For another case, Attribute-Based Encryption etc. require multi-pairing calculation.

Regarding (B), calculation speedup, the optimum implementation with a fixed parameter 
differs depending on the implementation environment, and we decided that it should not be standardized. 
For example, scalar multiplication of elliptic curves has differences 
such as using a different window size depending on the bit length the implementation environment supports.

Best Regards,
SAITO Tsunekazu

From: Kobi Gurkan <[email-masked]>
Sent: Friday, September 6, 2019 8:50 PM
To: Paterson Kenneth <[email-masked]>
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

Hi,

Seems like a good idea to have recommendations for pairing friendly curves for a variety of use-cases.

I want to suggest describing additional topics:
1. Products of pairings/multi-pairings - Many implementations of pairing-based protocols use these optimizations, so maybe it's worth discussing the way to do it.
2. More curves being used in the wild - BLS12-377 and SW6 (Cocks-Pinch curve whose order is the BLS12-377 base field) described in Zexe and used in Celo, MNT4753/MNT6753 cycle of curves used in Coda.

Kobi

On Fri, Sep 6, 2019 at 2:37 PM Paterson Kenneth <mailto:[email-masked]> wrote:
Dear CFRG,

Thanks,

Kenny (for the chairs)

mailto:[email-masked]

---

From: SAITO Tsunekazu <[email-masked]>
Date: Thu, 19 Sep 2019 20:55:18 +0900

Dear Riad, Kobi

This is Tsunekazu SAITO.

I also think that it is very important to decide which curve is listed and which is not listed, 
as Riad and Kobi say. We also investigated the implementation of pairing.
There are a large number of pairing implementations:

URL: https://docs.google.com/spreadsheets/d/e/2PACX-1vRhMzGruI5BU3ovp-83CbwG9yrmaU6XIweXv_-0uS3Kl_KUSmPLpmNJzU7mpUwqq-ysKJHSMMRABhU-/pubhtml?gid=1569286446&single=true

At IETF105, Shoko talked in detail about the significance of this draft for pairing, 
here I would like to explain the reasons for selecting the curves listed above.

(1) One reason is because the curve is widely used and is expected to be used in the future. 
Therefore, the BLS12-381 curve originally is cited and selected in the draft of BLS signature and HashingToCruve. 
Furthermore, I think that there is a possibility that it may be used in a signature ECDAA in TCG that is very similar to the BLS signature. 

(2) As the 2nd reason, the curve is selected so that it can be changed 
as smoothly as possible from the parameter BN254 etc. that have been used before. 
If one implemented BN254 curve, the cost of chaning from BN254 to BN462 can be reduced. 
Therfore, BN462 is listed. 

Therefore, we selected the two parameters, BLS12-381 and BN462, for describing 128-bit secure parameters. 
If there will be a curve that matches these reason and has strong influence 
for some protocol in the future, we should describe the detail parameter of the curve under many hum. 
On the other hand, it is very important to decide whether or not to publish for the rapid progress of the draft.

Of course, other curves such as BLS12-377 will be included in the usage list.

Best Regards,
Tsunekazu 

From: Kobi Gurkan <[email-masked]> 
Sent: Wednesday, September 11, 2019 7:47 PM
To: Riad S. Wahby <[email-masked]>
Cc: Paterson Kenneth <[email-masked]>; [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

Riad makes a good point. Maybe a SNARK-specific draft could be a better place.

On Mon, Sep 9, 2019 at 8:04 AM Riad S. Wahby <mailto:[email-masked]> wrote:

-=rsw

---

From: Rene Struik <[email-masked]>
Date: Thu, 19 Sep 2019 10:09:15 -0400

Hi Saito:

Indeed, there are trade-offs with the various data conversion methods. 
In my curve draft (Annex J.4 [1]) I used method B, as does the SIKE PQC 
submission to NIST's post-quantum contest. My choice mostly motivated by 
desire for consistency (so that others could simply cross-reference 
this) and extreme ease in processing (and can be easily implemented 
securely).

Best regards, Rene

Ref:
[1]https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-08#page-53
[2] Supersingular Isogeny-Based DH - SIDH-spec (David Jao et al, NIST 
PQC Project, November 30, 2017)

---

From: SAITO Tsunekazu <[email-masked]>
Date: Fri, 20 Sep 2019 16:30:16 +0900

Dear Rene 

Thank you for the information about your draft.
We also know that the BLS signature implementation uses concatenation.

Like these implementations of conversion by concatenation, 
this draft should be adapted to the method of concatenation. 
We will change to Method B.

Moreover, now there are two conversion methods of extension field element.
Thus we will add a remark  so that implementer will not make a mistake.

Best Regards,
Tsunekazu

From: Rene Struik <[email-masked]> 
Sent: Thursday, September 19, 2019 11:09 PM
To: SAITO Tsunekazu <[email-masked]>; [email-masked]
Subject: (offline) Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

Hi Saito:

Indeed, there are trade-offs with the various data conversion methods. In my curve draft (Annex J.4 [1]) I used method B, as does the SIKE PQC submission to NIST's post-quantum contest. My choice mostly motivated by desire for consistency (so that others could simply cross-reference this) and extreme ease in processing (and can be easily implemented securely). 

Best regards, Rene

Ref: 
[1]https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-08#page-53
[2] Supersingular Isogeny-Based DH - SIDH-spec (David Jao et al, NIST PQC Project, November 30, 2017)

Best Regards,
SAITO Tsunekazu

-----Original Message-----
From: Rene Struik mailto:[email-masked] 
Sent: Friday, September 6, 2019 10:52 PM
To: Paterson Kenneth mailto:[email-masked]; mailto:[email-masked]
Cc: mailto:[email-masked]; mailto:[email-masked]
Subject: Re: [Cfrg] Call for adoption: draft-yonezawa-pairing-friendly-curves

Dear colleagues:

Section 2.5:

Best regards, Rene

https://datatracker.ietf.org/doc/draft-yonezawa-pairing-friendly-curve
s/

Thanks,

Kenny (for the chairs)

--
email: mailto:[email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

-- 
email: mailto:[email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363