Re: [Cfrg] I-D Action: draft-kasamatsu-bncurves-00.txt

[Kohei Kasamatsu <[e-mail]>]

Hello Mike


> It’s cool to see pairing-friendly curves specced.  I’ve always found
> the applications of these curves fascinating, so progress toward
> deploying them is very nice to see.

Thank you for your feedback on the activities.
We are glad if we contribute to progress of the applications of these 
curves with you.


> But isn’t 512 bits rather large for a BN curve?  If you’re going to
> have a curve that large, it seems to me that you’d want an embedding
> degree of at least 18 even though it costs you a giant cofactor.  A
> curve with a 512-bit prime and a 384-bit subgroup might get you to
> the 192-bit security level.  This would take a 640-bit BN curve at
> minimum, with 720 a more conservative guess.
>
> Source: Freeman 2006, http://eprint.iacr.org/2006/372.pdf.  My
> knowledge on this subject is dated, so I’m sure you know better...

Thank you for your comments and information on security of our memo.

Our memo specifies parameters for compatibility with ISO/IEC document 
and parameters for high performance. 512-bit curve and 384-bit curves 
which are compliant with ISO/IEC have 128 security levels because of the 
following reason.

-----
We need to consider security on point of an elliptic curve and output of 
pairing, respectively ECDLP and FFDLP.
Table 1 shows correspondence between security level and p-elliptic curve 
against Pollard-rho attack. This is attack which must be considered in 
NIST-curve and so on.
Furthermore, table 1 shows correspondence between security level and 
output of pairing whose space is F_{p^k} against Number Field Sieve 
method, where k is called as an embedding degree.

Table 1
Security level (bit) | size of prime p (bit) | size of p^k
      128             |          256          |     3072
      192             |          384          |     7680
      256             |          512          |     15360

On the other hands, table 2 shows a prime p and size of output of 
pairing because BN-curves have embedding degree k=12.

Table 2
size of prime p (bit) | size of p^k   |
        256            |     3072      |
        384            |     4608      |
        512            |     6144      |

As table 1 and 2, sizes of p^k of 384-bit and 512-bit bn-curves are 
lower than sizes for security level 192-bit. Hence we evaluate that 
384-bit and 512-bit bn-curves have 128 security level. (advantage of 
bn-curve is that its embedding degree is optimal for obtaining security 
level 128-bit)
-----

If there are parameters of bn-curves with higher security level and high 
performance, we would like to add it into our memo.


Cheers,
Kohei KASAMATSU


(2014/01/23 9:46), Michael Hamburg wrote:
> Hello Kohei and company,
>
> It’s cool to see pairing-friendly curves specced.  I’ve always found the applications of these curves fascinating, so progress toward deploying them is very nice to see.
>
> But isn’t 512 bits rather large for a BN curve?  If you’re going to have a curve that large, it seems to me that you’d want an embedding degree of at least 18 even though it costs you a giant cofactor.  A curve with a 512-bit prime and a 384-bit subgroup might get you to the 192-bit security level.  This would take a 640-bit BN curve at minimum, with 720 a more conservative guess.
>
> Source: Freeman 2006, http://eprint.iacr.org/2006/372.pdf.  My knowledge on this subject is dated, so I’m sure you know better...
>
> Cheers,
> — Mike Hamburg
>
> On Jan 22, 2014, at 4:04 PM, Kohei Kasamatsu <[e-mail]> wrote:
>
>> Hi cfrg folks,
>>
>>
>> Elliptic curves with a special map called a pairing allow cryptographic
>> primitives to achieve functions or efficiency which cannot be realized
>> by conventional mathematical tools. For example, ZSS signature is one of
>> these primitives.
>>
>> We have recently submitted an I-D on Barreto-Naehrig curves (BN-curves)
>> which provide efficient operations of a pairing.
>> The I-D specifies parameters of BN-curves which are particularly useful
>> for realization of efficient cryptographic schemes based on pairing and parameters of BN-curves which are compliant with ISO/IEC 15946-5.
>>
>> We will propose I-Ds on computation of pairing and pairing-based primitives in order to contribute to IETF community in the near future.
>>
>> We would appreciate your comments and suggestions on our I-D and works.
>>
>> Best,
>> Kohei KASAMATSU
>> -------- Original Message --------
>> Subject: I-D Action: draft-kasamatsu-bncurves-00.txt
>> Date: Thu, 09 Jan 2014 21:13:03 -0800
>> From: [e-mail]
>> Reply-To: [e-mail]
>> To: [e-mail]
>>
>>
>> A New Internet-Draft is available from the on-line Internet-Drafts directories.
>>
>>
>>         Title           : Barreto-Naehrig Curves
>>         Authors         : Kohei Kasamatsu
>>                           Satoru Kanno
>>                           Tetsutaro Kobayashi
>>                           Yuto Kawahara
>> 	Filename        : draft-kasamatsu-bncurves-00.txt
>> 	Pages           : 15
>> 	Date            : 2014-01-09
>>
>> Abstract:
>>    Elliptic curves with pairing are useful tools for constructing
>>    cryptographic primitives.  In this memo, we specify domain parameters
>>    of Barreto-Naehrig curve (BN-curve) [5].  The BN-curve is an elliptic
>>    curve suitable for pairings and allows us to achieve high security
>>    and efficiency of cryptographic schemes.  This memo specifies domain
>>    parameters of two 254-bit BN-curves [1] [2] which allow us to obtain
>>    efficient implementations and domain parameters of 224, 256, 384, and
>>    512-bit BN-curves which are compliant with ISO/IEC 15946-5[3].
>>    Furthermore, this memo organizes differences between types of
>>    elliptic curves specified in ISO document and often used in open
>>    source softwares, which are called M-type and D-type
>>    respectively[21].
>>
>>
>> The IETF datatracker status page for this draft is:
>> https://datatracker.ietf.org/doc/draft-kasamatsu-bncurves/
>>
>> There's also a htmlized version available at:
>> http://tools.ietf.org/html/draft-kasamatsu-bncurves-00
>>
>>
>> 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]
>> http://www.irtf.org/mailman/listinfo/cfrg
>
>


-- 
Kohei KASAMATSU

NTT Software Corporation
TEL: [phone] FAX: [phone]
E-mail: [e-mail]