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

[Shoko YONEZAWA <[e-mail]>]

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 <[e-mail]> 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 <[e-mail]>
>> 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: [e-mail]
>>> Reply-To: [e-mail]
>>> To: [e-mail]
>>>
>>>
>>> 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
>>> [e-mail]
>>> 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
>>> [e-mail]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>>
> 

-- 
Shoko YONEZAWA
Lepidum Co. Ltd.
[e-mail]
TEL: [phone]