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

Michael Scott <mike.scott@miracl.com> Fri, 19 July 2019 14:23 UTC

Return-Path: <mike.scott@miracl.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 91A251202C9 for <cfrg@ietfa.amsl.com>; Fri, 19 Jul 2019 07:23:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.989
X-Spam-Level:
X-Spam-Status: No, score=-1.989 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, 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] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=miracl.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 Az5aPb6IHHvl for <cfrg@ietfa.amsl.com>; Fri, 19 Jul 2019 07:23:10 -0700 (PDT)
Received: from mail-io1-xd2b.google.com (mail-io1-xd2b.google.com [IPv6:2607:f8b0:4864:20::d2b]) (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 1A9F81202C6 for <cfrg@irtf.org>; Fri, 19 Jul 2019 07:23:10 -0700 (PDT)
Received: by mail-io1-xd2b.google.com with SMTP id o9so58835101iom.3 for <cfrg@irtf.org>; Fri, 19 Jul 2019 07:23:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=miracl.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=+AVPfdUIyd3ckDzNF3cL7xKSqNnj1AiJQhI651PbRgk=; b=g/iPBl+dx9WL+qRKFWbZya/2ArJYaMCOpIZ/+neJralW7KTLIMxSL/2hU5QE2M4qAx sXUIENJvhHgjbQ1p0zzlxfl97BnK/VuqMXcaexFTtLFcX1O7c8pJA2iuMA+6yFAOsd43 oREiz/4WA6CL2w04+toN98fLbg3sTz4jHjrmFzHl1fHChSkgE4SSmnxj4CRWZgkN8S0C DnYB1l7UoSCPTHCe1R9nKsxqAN1jocQqIlscN8eyOw4d5AI2AA4jl7hRiym9p9OYTZcz 8QmpRUagQ4UYqVUPX4bwxzZ87alWwmTrl+5pVMjva2AC97oWurVKuAI+N7cBQETY1MA2 IgCg==
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=+AVPfdUIyd3ckDzNF3cL7xKSqNnj1AiJQhI651PbRgk=; b=dEpWcNB4vn431eEsKDSvxonNuDfBHpaC5IoZiZ0RfaPxD+sNbjQWO/rtPfLXQnZhF6 KP9YWFQGUOf4Y0IA0PVBEbFWozdeohCcg5wH4SR64XedZAgywZj3WucCx112L9JlphtU IaVj/yhHsj6of8jiIfN9491CEjMEaFu3BWMyM1HBxCIr6G0rIK8PUvn1zqrhp8JSpoQb s+txdXgwuvYxV6ZtG/HzYwJQZRVsT13kzwfm788Qa62i5kbwkX1yBbXEx0M5otsZtmaP DaDiiTdffGgACIG0MsCu6X8vlHeg3vsQuHaVvCjb3tuYOgG+K+PpcOTBaEHlY3yupvXb jguA==
X-Gm-Message-State: APjAAAUFOrFUlj2vLvSIkN/ZZaEC1sAIYI7E1970y3eeAeRV+6zleDAl cowixDQMf+QbyqmummCZv4/M0pJopuld0fVJLoNq/8t1c28=
X-Google-Smtp-Source: APXvYqxCr8ZsNWCwE1ypZ9Xq8F//x/6ZqfUFohxio8GpH+NXKiOKaFSRi4oZmg0zG+uVI4YRFPRRgJ9M4BR3E5cvkgc=
X-Received: by 2002:a02:ccd2:: with SMTP id k18mr55605705jaq.3.1563546188752; Fri, 19 Jul 2019 07:23:08 -0700 (PDT)
MIME-Version: 1.0
References: <156258578868.734.4792662872752056842@ietfa.amsl.com> <37e46e43-cb4b-990c-b697-5cb14eae9a53@lepidum.co.jp>
In-Reply-To: <37e46e43-cb4b-990c-b697-5cb14eae9a53@lepidum.co.jp>
From: Michael Scott <mike.scott@miracl.com>
Date: Fri, 19 Jul 2019 15:21:03 +0100
Message-ID: <CAEseHRr3wUttdCK2dZ3riRue8rUeW3tqS0T15qjfoTLR4LqnGA@mail.gmail.com>
To: Shoko YONEZAWA <yonezawa@lepidum.co.jp>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000002bc5a9058e09773a"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/0Ms6CmcOlsnZ1WyBjbLdoh8t8jc>
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: Fri, 19 Jul 2019 14:23:13 -0000

 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
>