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, 05 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 >
- [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-fr… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Marek Jankowski