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

[Michael Scott <[e-mail]>]

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
>