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

[Michael Scott <[e-mail]>]

.. as a follow up to my comments on the curve BN462..

I note this choice

F_p6 = F_p2[v] / (v^3 - u - 2)


Its not clear to me why you did not choose the simpler irreducible
polynomial

x^6-(1+sqrt(-1))

which will always be more efficient. See the section on "BN towers" in
https://eprint.iacr.org/2009/556.pdf

where the conditions for this choice are satisfied.

  – If x0 ≡ 7 or 11 mod 12 then x^6 − (1 + √ −1) is irreducible over Fp2 =
Fp( √ −1).

(in the case of BN462 x0=7 mod 12)

Mike


On Sun, Mar 31, 2019 at 8:28 PM Michael Scott <[e-mail]> wrote:

> Hello Shoko,
>
> Thanks for previous clarifications.
>
> I am a bit puzzled by the proposed BN462 curve
>
> You chose the curve E:y^2=x^3+5
> On the twisted curve you choose E':y^2=x^3-u+2 (and I am unclear where
> -u+2 came from)
>
> In the paper that first suggested the curve -
> https://eprint.iacr.org/2017/334.pdf
>
> the authors suggest
> E: y^2=x^3-4, and
> E': y^2=x^3-4(1+u)
>
> which seems simpler, and closer to the BLS381 approach
>
> I am attempting to implement these curves (and already have BLS381 done).
> Any help is much appreciated.
>
> Mike
>
> On Fri, Mar 29, 2019 at 10:03 AM Shoko YONEZAWA <[e-mail]>
> wrote:
>
>> 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]
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>