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

Marek Jankowski <mjankowski309@gmail.com> Thu, 05 September 2019 14:27 UTC

Return-Path: <mjankowski309@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 230B8120091 for <cfrg@ietfa.amsl.com>; Thu, 5 Sep 2019 07:27:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.737
X-Spam-Level:
X-Spam-Status: No, score=-1.737 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_KAM_HTML_FONT_INVALID=0.01, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UuoCcrXM8C-Y for <cfrg@ietfa.amsl.com>; Thu, 5 Sep 2019 07:27:56 -0700 (PDT)
Received: from mail-io1-xd2e.google.com (mail-io1-xd2e.google.com [IPv6:2607:f8b0:4864:20::d2e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BA988120026 for <cfrg@irtf.org>; Thu, 5 Sep 2019 07:27:56 -0700 (PDT)
Received: by mail-io1-xd2e.google.com with SMTP id x4so5215996iog.13 for <cfrg@irtf.org>; Thu, 05 Sep 2019 07:27:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=yrhfVpKm6ItjHPNAmCnlHC09DM9+UIj6A/8pllJ+yOE=; b=bUI+YcyQ/mkjB32jsgW8aiwgQsn/BDPR+HK/r+H6/94zLslrumIuPoHLdLwkslii9g rWxcu0DtspqttgEFNc3p5BLrl6lUGpqYCkvvw0hlYZDmNSvIOTlO9XE7H9YmfWWKloKR VmC8s0sDKUFRtAE+frkkVaaFH97H3vxZciQhiSBXBKXNxHJC2fv37Lr8Z8ecXekNlxWV P3T0TQa+zYYIXuc2S5di5NQ5DqtKQzTDF+TQGwb9nN1g8Qwf4v3XPEabbf5eA2jz152D I3IizWRgNd49BorYWr0qE+CEbvY84tpSVIhVciIOGSG7Q5gyXw+PJA3z9UHVB9niCfdX NnfA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=yrhfVpKm6ItjHPNAmCnlHC09DM9+UIj6A/8pllJ+yOE=; b=joJUxXNgYU1zS5P1UoIm0AaEi4rdgVZUGByG30fqRzSqLLH/wVbnHwlFhh/IQV1YIx RyfX21S1RfZ6QOM+/WafqUoOGk8BQSOL+M7QaofS1ZwyKyFQevltBxT+3wWrt4JDFiht Kd/0LEm5Qsu/XOTP5QIwvOF0QOH/EHW0fA4QTUFlX0Oe76fyyM607MJj75ZF0ffhaK1N nyyNAzi9CBHtLJD1wo387waYqT8ESyaL3rOKTHeq+wFcHglWyZWa1YEmxV05O5rMXeMu RRPTera745cUmwJu7eBCgJWdB6rWS1chALgtCBAQITKKz/5JMyhUbujMZjSSQENtjOUh R+Ig==
X-Gm-Message-State: APjAAAWOOfQNwGkDyjVdcNxIuSebhsXzxKwbPmMPAZJjhyrSjHjBkvJ5 W6lAytyGU+3WxxS/kvwDShKUsZfdWDSawUb5nkKKyQl8
X-Google-Smtp-Source: APXvYqwmnZpE6qotbu60mZ45nvm6SCYFvzKnXBvAAUoZO2aOSFJSoqUjxenuza1ZcGYkvZwLVagv3H59Ef7wct/21ME=
X-Received: by 2002:a5e:c248:: with SMTP id w8mr4267104iop.246.1567693676048; Thu, 05 Sep 2019 07:27:56 -0700 (PDT)
MIME-Version: 1.0
References: <156258578868.734.4792662872752056842@ietfa.amsl.com> <37e46e43-cb4b-990c-b697-5cb14eae9a53@lepidum.co.jp> <CAEseHRr3wUttdCK2dZ3riRue8rUeW3tqS0T15qjfoTLR4LqnGA@mail.gmail.com>
In-Reply-To: <CAEseHRr3wUttdCK2dZ3riRue8rUeW3tqS0T15qjfoTLR4LqnGA@mail.gmail.com>
From: Marek Jankowski <mjankowski309@gmail.com>
Date: Thu, 5 Sep 2019 16:27:36 +0200
Message-ID: <CAMCcN7S5DhPMZAFGtwcCgb7X00pqH=zBzdkpULiU0qmbon59hg@mail.gmail.com>
To: Michael Scott <mike.scott@miracl.com>
Cc: Shoko YONEZAWA <yonezawa@lepidum.co.jp>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000ad770d0591cf2025"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/bsGgc67kEsj6xNxEJ5Uoi2Vqaxg>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-02.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 05 Sep 2019 14:27:59 -0000

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 <mike.scott@miracl.com>; 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 <yonezawa@lepidum.co.jp>;
> 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: internet-drafts@ietf.org
>> Reply-To: internet-drafts@ietf.org
>> To: i-d-announce@ietf.org
>>
>>
>> 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
>> I-D-Announce@ietf.org
>> 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
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>