Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.txt
Shoko YONEZAWA <yonezawa@lepidum.co.jp> Thu, 28 March 2019 07:27 UTC
Return-Path: <yonezawa@lepidum.co.jp>
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 01E3912024B for <cfrg@ietfa.amsl.com>; Thu, 28 Mar 2019 00:27:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=lepidum-co-jp.20150623.gappssmtp.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 czBDdZBJ2YMQ for <cfrg@ietfa.amsl.com>; Thu, 28 Mar 2019 00:27:02 -0700 (PDT)
Received: from mail-pg1-x535.google.com (mail-pg1-x535.google.com [IPv6:2607:f8b0:4864:20::535]) (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 42D32120252 for <cfrg@irtf.org>; Thu, 28 Mar 2019 00:27:02 -0700 (PDT)
Received: by mail-pg1-x535.google.com with SMTP id y3so11191798pgk.12 for <cfrg@irtf.org>; Thu, 28 Mar 2019 00:27:02 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lepidum-co-jp.20150623.gappssmtp.com; s=20150623; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=01clFsX8vr22NYRS/A8OrxeSUzBsA1+F9g+z4PciRSU=; b=XTzzs14GILcyMAhEYOc3sCQTB75i6zAlzT9LJmoxHa+errJKbifmKrzCJRzPtyz64V 7KndQiENd42Ui8ZRguSrIDifGe9qm++5ATvyeP+2uGyvhZnUwQwO7tD9IFG7yly28wCX x3bVO2lszBcWs2/Q40dUvT67m8nN06bORO40LU7K5PDMhssY30aUVe6pcu+Y5xLPc7he Nob2n50EfoHbvbz3KBVHh9fmTLrsbktlm1XerUmwW6F28GhFd4OGDs4bvuu0EDkRMxVK TCgUWSt901YJCBVf8FZAtMH6k7l2wQ2vT7S5D43+tznMgKt1Xa3gZ+PmdmkwvNbuV4R+ ypcQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=01clFsX8vr22NYRS/A8OrxeSUzBsA1+F9g+z4PciRSU=; b=gd22FppLUc/UjzgyHXXMzjHm1TYU2fVMmFwyrt2DxxvPc0sALUw2Z0OkC1Hv2LzWQ1 VZPkj2L8Fmy05Mep14oTZEltjrgz6mI7J2m2WqL2HBpGBW/4T2C0DTmvHlYgWYQJobvn Ve4844O/9TlA1cxXcnLbAQKI7ZYCVKRMhZELTEdBXjYQLn3sR73O4B3eNYoSup4n4th8 SAe6GDl1SncDjlDTdC+j5k485CxoBvu0W5OHWqSyHpodFFR/XzEuXr1iN9aLjD1khIVi ZEYtA+VsqkAs0ApCQVaz9G40vupgdcID7tOJqedb1ti3B7e2VI++P9ZSJWBEIaMKzljA O2YA==
X-Gm-Message-State: APjAAAWNUe9f2lCdnvB97wMcSu0GQefa27om7SM6LZS13A+cBYuRxFvE qV5G3szczjczzE1861711dvarNOesgHgzOUtAQG1waZGpuJeJAAMBwQyHeVNFDUxlELZVq6dFwK CMw0iAFwPy9BPxgEtfXTK6W839nQ/jZzCQZ0oLDBZb6oHl1XxSls3hhPDHEY=
X-Google-Smtp-Source: APXvYqzJYMA/HYSYqwPELk0CmLojjHSHcaBH4/+gF90WsrhgfoGJENoxwJd6qc0HsPy8umGMDpm2wQ==
X-Received: by 2002:a63:36cb:: with SMTP id d194mr10920170pga.426.1553758021428; Thu, 28 Mar 2019 00:27:01 -0700 (PDT)
Received: from [192.168.30.77] ([150.249.212.66]) by smtp.gmail.com with ESMTPSA id i135sm26842327pgd.41.2019.03.28.00.27.00 for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 28 Mar 2019 00:27:00 -0700 (PDT)
To: cfrg@irtf.org
References: <155231848866.23086.9976784460361189399@ietfa.amsl.com> <737ea2b3-74e3-d02e-a44d-c44cca5db036@lepidum.co.jp> <CAEseHRrSiJ72tQepyTiL=pSBcRRLGXhnJyy_QzOubWax+v=Ntw@mail.gmail.com> <CAEseHRqh4d0VaeSaj4CWr_ZxJbbpm33ZaLF-aYGBjVowFNLFeQ@mail.gmail.com> <c57bbf7b-3177-eb64-a3c0-26842fccbb89@lepidum.co.jp> <CAEseHRrVomCo6KD7gidCRBzKJDzFZRQ+q0+PjfBr8tQT4dVpMQ@mail.gmail.com>
From: Shoko YONEZAWA <yonezawa@lepidum.co.jp>
Message-ID: <b016d1f6-68e4-9728-c738-ab72c593dfd1@lepidum.co.jp>
Date: Thu, 28 Mar 2019 16:26:58 +0900
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.0
MIME-Version: 1.0
In-Reply-To: <CAEseHRrVomCo6KD7gidCRBzKJDzFZRQ+q0+PjfBr8tQT4dVpMQ@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/t5VOHUtVm3pq2rqN-bfwiuXQsKc>
Subject: Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairing-friendly-curves-01.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, 28 Mar 2019 07:27:06 -0000
Hi Mike, Thank you again for the feedback. > 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. As the information for implementers, we add the description of M-type or D-type for each curve. > 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. The generator point for G2 is described as a base point G' = (x', y') in our draft. We revise the description for clarification. Best, Shoko On 2019/03/21 0:48, Michael Scott wrote: > 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 <yonezawa@lepidum.co.jp> > 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 <mike.scott@miracl.com> >> 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 <yonezawa@lepidum.co.jp >>> >>>> 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: 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 >>>>> 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 >>>>> 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 >>>>> >>>> >>> >> >> -- >> Shoko YONEZAWA >> Lepidum Co. Ltd. >> yonezawa@lepidum.co.jp >> TEL: +81-3-6276-5103 >> > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > -- Shoko YONEZAWA Lepidum Co. Ltd. yonezawa@lepidum.co.jp TEL: +81-3-6276-5103
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Marek Jankowski
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- [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… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… David Wong
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Paterson Kenneth
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… John Mattsson
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Marek Jankowski
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Dan Brown
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… John Mattsson
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… denis bider
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Peter Gutmann
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Peter Gutmann
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Björn Haase
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Peter Gutmann
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… William Whyte
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Watson Ladd
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Watson Ladd
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… John Mattsson
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Damien Miller
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Peter Gutmann
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Ruslan Kiyanchuk
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… mcgrew
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Paterson Kenneth
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… mcgrew
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Peter Gutmann
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… A. Huelsing
- Re: [Cfrg] I-D Action: draft-yonezawa-pairing-fri… Paul Hoffman
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Salz, Rich
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Paterson Kenneth
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Shoko YONEZAWA
- Re: [Cfrg] Fwd: I-D Action: draft-yonezawa-pairin… Michael Scott