Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

["Blumenthal, Uri - 0553 - MITLL" <[e-mail]>]

Naïve question: how is this approach supposed to weather in post-quantum world? 

 

From: Cfrg <[e-mail]> on behalf of Marek Jankowski <[e-mail]>
Date: Thursday, March 28, 2019 at 07:56
To: "[e-mail]" <[e-mail]>
Cc: CFRG <[e-mail]>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt

 

Dear Shoko,

 

I am supportive of this work. Pairings give rise to useful cryptographic primitives and so should be well standardized.

Please find below some minor comments and questions about the I-D.

 

Section 1.1 - "The cryptographic algorithms [...] is widely used" should be "The cryptographic algorithms [...] are widely used", and a bit later "a variant [...] is attracted the attention" should be 

"a variant [...] has attracted the attention"..

 

In the last sentence of the section, "several applications [...] is now in practical use." should be replaced with  "several applications [...] are now in practical use."

 

Section 2.1 - as there are several variants for elliptic curves, it may be kind to remind the reader that the specified equation is the Weierstrass form.

Also, A and B satisfy the discriminant inequality (and not "satisfies"). "the line that intersects P and Q" should be "the line that passes through P and Q".

 

I personally feel it is redundant to thoroughly explain the addition law of the EC group, but if such care is taken, then I think it is a good idea to also specify doubling, i.e. P+P.

 

While defining the BN and BLS curves (Sections 2.3, 2.4), formulae are given for p and r as a function of t, and it says that t should be chosen "well". What makes a choice

of t good? Is it sufficient to require p and r to be prime?

 

In the Appendix, it would be good practice to specifically mention that for most uses, calculations should be done in constant time.

 

In addition, I found it difficult to follow the properties required from s and s_i (apart from sum s_i * 2^i = s). Do different choices give rise to different pairings?

Or is it an efficiency issue? 

 

Thank you,

 

Marek.

 

On Thu, Mar 28, 2019 at 12:12 PM Michael Scott <[e-mail]> wrote:

OK. However for the BL381 curve for example the G2 generator point does not appear to be the same as the one given here... 

 

https://github.com/zkcrypto/pairing/tree/master/src/bls12_381 

 

Also it would help if the individual components of x' and  y' were highlighted. For example if x'=a'u+b' it would be useful to know were a' ends and b' begins. 

 

 Also as in the above link it would I think be good practice to state exactly how the values for G1 and G2 were arrived at.

 

Mike

 

On Thu, Mar 28, 2019 at 7:27 AM Shoko YONEZAWA <[e-mail]> wrote:

Hi Mike,

Thank you again for the feedback.

 > It would be helpful for implementors to know if the curves support an
 > M-Type or D-Type twist.
 >
 > BLS381 and BN462 are both M-Type. BLS48_581 is D-Type.

As the information for implementers,
we add the description of M-type or D-type for each curve.

 > Also I think a standard should also include a generator point for G2 for
 > interoperability, as well as for G1. For example an implementation of BLS
 > short signature probably requires a generator in G2.

The generator point for G2 is described as a base point G' = (x', y')
in our draft.
We revise the description for clarification.

Best,
Shoko

On 2019/03/21 0:48, Michael Scott wrote:
> A couple of further observations..
> 
> It would be helpful for implementors to know if the curves support an
> M-Type or D-Type twist.
> 
> BLS381 and BN462 are both M-Type. BLS48_581 is D-Type.
> 
> Also I think a standard should also include a generator point for G2 for
> interoperability, as well as for G1. For example an implementation of BLS
> short signature probably requires a generator in G2.
> 
> Mike
> 
> On Tue, Mar 19, 2019 at 3:39 AM Shoko YONEZAWA <[e-mail]>
> wrote:
> 
>> Dear Mike,
>>
>> Thank you very much for your comments.
>>
>>> The suggested curves do not appear to meet the requirement for subgroup
>>> security which is indicated as being a desirable property in section
>> 3.1 -
>>> “One has to choose parameters so that the cofactors of G_1, G_2 and G_T
>>> contain no prime factors smaller than |G_1|, |G_2| and |G_T|”.
>>>
>>> The case could be made that subgroup security is not so important, but if
>>> so the text in 3.1 should be modified to reflect this point of view.
>>
>> As you pointed out, we found that our suggested curves are not
>> subgroup-secure.
>> For standardization, we focus on the existing implementations as well as
>> sufficient security.
>> We think it impractical to choose a completely new parameter and
>> implement it from now.
>> Therefore, we would like to recommend the current parameters we
>> described in the draft with modifying our description of subgroup security.
>>
>> We are keeping watching the research activity and ready to change
>> parameters if a critical attack for pairing-friendly curves which don't
>> meet subgroup security is found.
>>
>>> Another point – the BLS381 curve was chosen for a very particular (albeit
>>> important) application where it is a requirement that r-1 has a factor of
>>> 2^m for a large value of m. Curves chosen with application-specific
>>> benefits should I suggest be considered carefully if proposed as more
>>> general purpose standards. Note that this particular application
>>> disadvantages BN curves, as due to the form of its formula for r, this
>>> particular condition is much harder to achieve.
>>
>> We guess that BLS12-381 is chosen for the efficient computation of their
>> zero-knowledge proof. Nonetheless, we think BLS12-381 has sufficient
>> performance for general purpose.
>>
>> Best regards,
>> Shoko
>>
>> On 2019/03/15 3:52, Michael Scott wrote:
>>> Another point..
>>>
>>> For the BLS curves, the cofactor h in G_1 is calculated here as
>>> ((t-1)^2)/3, and this will work fine as a co-factor, where a random point
>>> on the curve over the base field can be multiplied by this co-factor to
>>> create a point of order r in G_1. But this co-factor is unnecessarily
>> large.
>>>
>>> The same can be achieved by using (t-1) as a co-factor, due to the
>>> structure of pairing friendly fields. This will be twice as fast.
>>>
>>>
>>> Mike
>>>
>>>
>>> However to
>>>
>>> On Thu, Mar 14, 2019 at 3:21 PM Michael Scott <[e-mail]>
>> wrote:
>>>
>>>> Hello,
>>>>
>>>> I greatly welcome this proposal, and would not want to slow its progress
>>>> in any way. It is long overdue that pairing-friendly curves be
>>>> standardized, before unsuitable de-facto standards emerge, which may
>> not be
>>>> ideal, but which may nevertheless become widely deployed.
>>>>
>>>> However I make the following observations about the particular curves
>>>> suggested.
>>>>
>>>> The suggested curves do not appear to meet the requirement for subgroup
>>>> security which is indicated as being a desirable property in section
>> 3.1 -
>>>> “One has to choose parameters so that the cofactors of G_1, G_2 and G_T
>>>> contain no prime factors smaller than |G_1|, |G_2| and |G_T|”.
>>>>
>>>> The case could be made that subgroup security is not so important, but
>> if
>>>> so the text in 3.1 should be modified to reflect this point of view.
>>>>
>>>> The curve BN462 is not sub-group secure, as in G_T (p^4-p^2+1) /r has
>>>> small factors of 2953, 5749 and 151639045476553 (amongst others). I
>> didn’t
>>>> check G_2.
>>>>
>>>> The curve BLS381 has the same problem, as (p^4-p^2+1) /r has small
>> factor
>>>> of 4513, 584529700689659162521 and more. Again I didn’t check G_2
>>>>
>>>> The curve BLS48-581 has the same problem, as (p^4-p^2+1) /r has a small
>>>> factor of 76369, and probably others. Again I didn’t check for G_2
>>>>
>>>> The draft does point out that for BLS curves, when hashing to a point in
>>>> G_1, multiplication by a small co-factor h>1 will always be necessary.
>>>>
>>>> In my opinion sub-group security in G_T is particularly important if it
>> is
>>>> desirable to offload the pairing calculation to an untrusted server,
>> and so
>>>> it is a feature I would consider useful in a standard curve. In our
>>>> experience finding such curves is relatively easy (although finding
>> curves
>>>> that are sub-group secure in both G_2 and G_T is more problematical).
>>>>
>>>> Another point – the BLS381 curve was chosen for a very particular
>> (albeit
>>>> important) application where it is a requirement that r-1 has a factor
>> of
>>>> 2^m for a large value of m. Curves chosen with application-specific
>>>> benefits should I suggest be considered carefully if proposed as more
>>>> general purpose standards. Note that this particular application
>>>> disadvantages BN curves, as due to the form of its formula for r, this
>>>> particular condition is much harder to achieve.
>>>>
>>>>
>>>> Mike
>>>>
>>>> On Wed, Mar 13, 2019 at 10:33 AM Shoko YONEZAWA <[e-mail]
>>>
>>>> wrote:
>>>>
>>>>> Hi there,
>>>>>
>>>>> Thank you for your comments to our pairing-friendly curve draft.
>>>>> We submitted a new version.
>>>>>
>>>>> According to Kenny's comments,
>>>>> we added the following description to the new version.
>>>>>
>>>>> - Pseudo-codes for pairing computation
>>>>> - Example parameters and test vectors of each curve
>>>>>
>>>>> We now published our working draft on GitHub,
>>>>> together with the BLS signature group.
>>>>> Please feel free to submit issues. Your comments are really
>> appreciated.
>>>>>
>>>>> https://github.com/pairingwg/pfc_standard/
>>>>>
>>>>> Best,
>>>>> Shoko
>>>>>
>>>>> -------- Forwarded Message --------
>>>>> Subject: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
>>>>> Date: Mon, 11 Mar 2019 08:34:48 -0700
>>>>> From: [e-mail]
>>>>> Reply-To: [e-mail]
>>>>> To: [e-mail]
>>>>>
>>>>>
>>>>> A New Internet-Draft is available from the on-line Internet-Drafts
>>>>> directories.
>>>>>
>>>>>
>>>>>            Title           : Pairing-Friendly Curves
>>>>>            Authors         : Shoko Yonezawa
>>>>>                              Sakae Chikara
>>>>>                              Tetsutaro Kobayashi
>>>>>                              Tsunekazu Saito
>>>>>           Filename        :
>> draft-yonezawa-pairing-friendly-curves-01.txt
>>>>>           Pages           : 28
>>>>>           Date            : 2019-03-11
>>>>>
>>>>> Abstract:
>>>>>       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.
>>>>>
>>>>>
>>>>> The IETF datatracker status page for this draft is:
>>>>>
>> https://datatracker...ietf.org/doc/draft-yonezawa-pairing-friendly-curves/
>>>>>
>>>>> There are also htmlized versions available at:
>>>>> https://tools.ietf.org/html/draft-yonezawa-pairing-friendly-curves-01
>>>>>
>>>>>
>> https://datatracker.ietf.org/doc/html/draft-yonezawa-pairing-friendly-curves-01
>>>>>
>>>>> A diff from the previous version is available at:
>>>>>
>>>>>
>> https://www.ietf.org/rfcdiff?url2=draft-yonezawa-pairing-friendly-curves-01
>>>>>
>>>>>
>>>>> Please note that it may take a couple of minutes from the time of
>>>>> submission
>>>>> until the htmlized version and diff are available at tools...ietf.org.
>>>>>
>>>>> Internet-Drafts are also available by anonymous FTP at:
>>>>> ftp://ftp.ietf.org/internet-drafts/
>>>>>
>>>>> _______________________________________________
>>>>> I-D-Announce mailing list
>>>>> [e-mail]
>>>>> https://www.ietf.org/mailman/listinfo/i-d-announce
>>>>> Internet-Draft directories: http://www.ietf.org/shadow.html
>>>>> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt
>>>>>
>>>>> _______________________________________________
>>>>> Cfrg mailing list
>>>>> [e-mail]
>>>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>>>
>>>>
>>>
>>
>> --
>> Shoko YONEZAWA
>> Lepidum Co. Ltd.
>> [e-mail]
>> TEL: [phone]
>>
> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
> 

-- 
Shoko YONEZAWA
Lepidum Co. Ltd.
[e-mail]
TEL: [phone]

_______________________________________________
Cfrg mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[e-mail]
https://www.irtf.org/mailman/listinfo/cfrg