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

[Shoko YONEZAWA <[e-mail]>]

Hi Mike,

This difference is probably caused by representation of an extension field.
We encoded the generator G' = (x', y') where x' = a'*u + b' and y' = 
c'*u + d' by

x' : a'*p + b' (in Z) and
y' : c'*p + d' (in Z),

whereas zkcrypto encoded it like

x' : a' || b' and
y' : c' || d'.

We followed the convention shown in IEEE 1363a-2004.

As you suggested, it is helpful to describe a',b',c',d' as well as x', y'.
We add these value in the next version.

Thank you again,
Shoko

On 2019/03/28 20:11, Michael Scott 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
> 

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