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

[Shoko YONEZAWA <[e-mail]>]

Dear Kenny,

Thank you for your suggestion.
Mike kindly agreed with our parameters this time,
and we would like to choose the one we described in our draft.

If there are suggestions for other parameters,
we will be happy to add them.

Regards,
Shoko

On 2019/04/23 22:59, Paterson  Kenneth wrote:
> Dear Shoko,
> 
> I think it's acceptable to describe a variety of different pairing parameters - some already deployed at scale, and some offering better efficiency/security trade-offs.
> 
> Regards,
> 
> Kenny
> 
> -----Original Message-----
> From: Cfrg <[e-mail]> on behalf of Shoko YONEZAWA <[e-mail]>
> Date: Monday, 22 April 2019 at 13:27
> To: "[e-mail]" <[e-mail]>
> Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
> 
>      Hello Mike,
>      
>      I'm sorry for being late for responding to your comments,
>      all of which are important and valuable.
>      Please allow me to reply to all of your comments in this single mail.
>      
>      Thank you for your suggestions of the curve parameters.
>      As you mentioned, there are the curve parameters which provide more
>      efficient computation than we described,
>      but we emphasize the implementation status, that is,
>      whether the curves have been already available.
>      
>      As for BN462, we refer to the parameters implemented in mcl
>      (https://github.com/herumi/mcl).
>      In this implementation, the twisted curve is set to E':y^2=x^3-u+2
>      and the tower of extension field is F_p6 = F_p2[v] / (v^3 - u - 2).
>      Their implementation of BLS12-381 has been adopted to Zcash
>      and we cannot ignore the curve parameters chosen in mcl.
>      Therefore, we would like to choose the existing curve parameters in our
>      draft in order for interoperability.
>      
>      We understand that the parameters you suggested can indeed improve the
>      efficiency.
>      We can add these parameters to our draft if it is accepted to describe
>      multiple parameters.
>      
>      I would be grateful if my answers could make sense.
>      
>      Best,
>      Shoko
>      
>      On 2019/04/03 18:08, Michael Scott wrote:
>      > .. 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]
>      > <mailto:[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] <mailto:[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] <mailto:[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] <mailto:[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] <mailto:[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] <mailto:[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]
>      >         <mailto:[e-mail]>
>      >          >>>>>>> Reply-To: [e-mail]
>      >         <mailto:[e-mail]>
>      >          >>>>>>> To: [e-mail] <mailto:[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/
>      >         <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 <http://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] <mailto:[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] <mailto:[e-mail]>
>      >          >>>>>>> https://www.irtf.org/mailman/listinfo/cfrg
>      >          >>>>>>>
>      >          >>>>>>
>      >          >>>>>
>      >          >>>>
>      >          >>>> --
>      >          >>>> Shoko YONEZAWA
>      >          >>>> Lepidum Co. Ltd.
>      >          >>>> [e-mail] <mailto:[e-mail]>
>      >          >>>> TEL: [phone]
>      >          >>>>
>      >          >>>
>      >          >>>
>      >          >>> _______________________________________________
>      >          >>> Cfrg mailing list
>      >          >>> [e-mail] <mailto:[e-mail]>
>      >          >>> https://www.irtf.org/mailman/listinfo/cfrg
>      >          >>>
>      >          >>
>      >          >> --
>      >          >> Shoko YONEZAWA
>      >          >> Lepidum Co. Ltd.
>      >          >> [e-mail] <mailto:[e-mail]>
>      >          >> TEL: [phone]
>      >          >>
>      >          >> _______________________________________________
>      >          >> Cfrg mailing list
>      >          >> [e-mail] <mailto:[e-mail]>
>      >          >> https://www.irtf.org/mailman/listinfo/cfrg
>      >          >>
>      >          >
>      >          >
>      >          > _______________________________________________
>      >          > Cfrg mailing list
>      >          > [e-mail] <mailto:[e-mail]>
>      >          > https://www.irtf.org/mailman/listinfo/cfrg
>      >          >
>      >
>      >         --
>      >         Shoko YONEZAWA
>      >         Lepidum Co. Ltd.
>      >         [e-mail] <mailto:[e-mail]>
>      >         TEL: [phone]
>      >
>      >         _______________________________________________
>      >         Cfrg mailing list
>      >         [e-mail] <mailto:[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
>      
> 

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