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

[Michael Scott <[e-mail]>]

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]
>