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

From: Marek Jankowski <[email-masked]>
Date: Thu, 5 Sep 2019 16:27:36 +0200

Dear Shoko,

I welcome the updated draft, and also have a few comments:

1. Firstly, some minor corrections
         a."embedded degree" should be "embedding degree" (p.4,5)
         b. "r-torsions points" should be "r-torsion points" (p.6)
         c. "based point" should be "base point" (p.9,12,14)
2. in addition, a couple of suggestions:
         a.* Libra*, Facebook's recently launched crypto currency, uses
BLS12-381 in its BFT  protocol. It should be included in the list of
implementations (p.18,19).
         b. Regarding Appendix A - *Computing optimal Ate-pairings*
                     i. Firstly, it should be clarified that the parameter
*t*, used for computing the pairing,  is also the one used in subsections
2.3 and 2.4 to determine the size of the
curve.
                    ii. Secondly, I suspect that for negative values of *s*,
an error occurs in the calculation the algorithm performs: along with
replacing T by -T, I think every s_i for i<L should be replaced by -s_i. I
may be off here, so it would be best for someone with more expertise on the
matter to look into it.
                   iii. Also, it would be nice to provide a reference that
gives a detailed account of the way to compute an optimal Ate pairing over
BLS curves (The reference [Ver09] deals with BN curves and some other
families, but not with BLS curves).

All in all I commend the effort, and do believe that we would do well to
make the draft a work item in the CFRG.

Marek.

On Fri, Jul 19, 2019 at 4:23 PM Michael Scott <[email-masked]> wrote:

>  Hello Shoko,
>
> I welcome your updated draft. A few observations..
>
> 1. The BLS48-581 curve uses a rather unfortunate form of towering. Whereas
> BLS12-381 and BN462 use irreducible polynomials of the form u^2-u-1,
> BLS48-581 uses irreducible polynomials with the opposite sign, e.g.
> u^2+u+1. This makes code re-use between curves awkward. It will be
> interesting to see what form is used for the proposed 192-bit curves
>
> 2. The BLS co-factor is still unnecessarily large, of the form (z-1)^2
> when z-1 is sufficient, and of lower Hamming weight. This point has also
> recently been made here https://eprint.iacr.org/2019/830 and here
> https://eprint.iacr.org/2019/403
>
> 3. All of these curves are now implemented in the most recent version (as
> yet unreleased) of our AMCL library. Some indicative timings are given
> below (Rust language version, no assembly, projective coordinates in G2).
> These should not be considered best-case absolute numbers, but may be
> useful for observing how the complexity of common pairing-based operations
> scale with increasing security.
>
>
> Testing/Timing bls12_381 Pairings
>
> G1 mul - 38639 iterations 0.26 ms per iteration
>
> G2 mul - 19596 iterations 0.51 ms per iteration
>
> GT pow - 14476 iterations 0.69 ms per iteration
>
> PAIRing ATE - 12211 iterations 0.82 ms per iteration
>
> PAIRing FEXP - 8430 iterations 1.19 ms per iteration
>
> All tests pass
>
>
> Testing/Timing bn462 Pairings
>
> G1 mul - 17290 iterations 0.58 ms per iteration
>
> G2 mul - 8666 iterations 1.15 ms per iteration
>
> GT pow - 6142 iterations 1.63 ms per iteration
>
> PAIRing ATE - 4991 iterations 2.00 ms per iteration
>
> PAIRing FEXP - 6591 iterations 1.52 ms per iteration
>
> All tests pass
>
>
> Testing/Timing bls48_581 Pairings
>
> G1 mul - 11667 iterations 0.86 ms per iteration
>
> G2 mul - 584 iterations 17.12 ms per iteration
>
> GT pow - 377 iterations 26.55 ms per iteration
>
> PAIRing ATE - 1078 iterations 9.28 ms per iteration
>
> PAIRing FEXP - 230 iterations 43.49 ms per iteration
>
> All tests pass
>
>
> At the 192-bit security level we have implemented our own bls24 curve
>
>
> Testing/Timing bls24 Pairings
>
> Modulus size 479 bits
>
> 64 bit build
>
> G1 mul - 17304 iterations 0.58 ms per iteration
>
> G2 mul - 3295 iterations 3.04 ms per iteration
>
> GT pow - 2202 iterations 4.54 ms per iteration
>
> PAIRing ATE - 3168 iterations 3.16 ms per iteration
>
> PAIRing FEXP - 1397 iterations 7.16 ms per iteration
>
> All tests pass
>
>
> Mike
>
>
>
> On Fri, Jul 19, 2019 at 4:27 AM Shoko YONEZAWA <[email-masked]>
> wrote:
>
>> Hi CFRG folks,
>>
>> Here is 02 version of our draft "Pairing-Friendly Curves."
>> We revised the draft with respect to your comments and feedback from the
>> mailing list.
>>
>> I am going to give a presentation about this draft at CFRG meeting in
>> Montreal.
>> Your further comments are greatly appreciated.
>>
>> See you in Montreal.
>>
>> Thanks,
>> Shoko
>>
>> -------- Forwarded Message --------
>> Subject: I-D Action: draft-yonezawa-pairing-friendly-curves-02.txt
>> Date: Mon, 08 Jul 2019 04:36:28 -0700
>> From: [email-masked]
>> Reply-To: [email-masked]
>> To: [email-masked]
>>
>>
>> A New Internet-Draft is available from the on-line Internet-Drafts
>> directories.
>>
>>
>>          Title           : Pairing-Friendly Curves
>>          Authors         : Shoko Yonezawa
>>                            Tetsutaro Kobayashi
>>                            Tsunekazu Saito
>>         Filename        : draft-yonezawa-pairing-friendly-curves-02.txt
>>         Pages           : 36
>>         Date            : 2019-07-08
>>
>> 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-02
>>
>> https://datatracker.ietf.org/doc/html/draft-yonezawa-pairing-friendly-curves-02
>>
>> A diff from the previous version is available at:
>>
>> https://www.ietf.org/rfcdiff?url2=draft-yonezawa-pairing-friendly-curves-02
>>
>>
>> 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
>> [email-masked]
>> 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
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>