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

From: Kohei Kasamatsu <[email-masked]>
Date: Tue, 04 Feb 2014 18:29:45 +0900

Hi Mike,

Thank you for your comments.

> There are no such BN curves.  I just don't expect that most
> implementers will consider using a 512-bit BN curve, because at that
> size a non-BN curve with k=18 or k=24 has a better trade-off of
> security vs performance.
> But I suppose that such curves might not be
> ISO/IEC compliant, because of their cofactors.

I misunderstood your intentions.

I also think it is better that we use non-BN curve with k=18 or k=24
if we need more higher security than 128-bit.
(For example, the comparison of [1] supports it:-) )

On the other hands, our I-D focuses on BN-curves, as you understand.
I hope new I-Ds which are submitted in the future will achieve the
requirement which you pointed out and such activities will become active.

And, although I also don't expect that most implementers will consider 
using a 512-bit BN curves which are specified in our I-D, we think it is 
valuable to provide parameters and additional information (on security 
and differences between M-type and D-type) of curves with international 
standard.

[1]  http://eprint.iacr.org/2012/232

Cheers,
Kohei KASAMATSU

(2014/01/30 3:31), Mike Hamburg wrote:
>
> On Jan 29, 2014, at 3:01 AM, Kohei Kasamatsu <[email-masked]> wrote:
>
>>> 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.
>> ...
>> If there are parameters of bn-curves with higher security level and high performance, we would like to add it into our memo.
>
>
> There are no such BN curves.  I just don't expect that most implementers will consider using a 512-bit BN curve, because at that size a non-BN curve with k=18 or k=24 has a better trade-off of security vs performance.  But I suppose that such curves might not be ISO/IEC compliant, because of their cofactors.
>
> Cheers,
> -- Mike
>
>
>

-- 
Kohei KASAMATSU

NTT Software Corporation
TEL: +81 45 212 7908 FAX: +81 45 212 9800
E-mail: [email-masked]

---

From: Kohei Kasamatsu <[email-masked]>
Date: Tue, 04 Feb 2014 18:30:01 +0900

Hi Laura,

Thank you for your feedback on it.

We will apply that modification to new version.

Best,
Kohei KASAMATSU

(2014/01/30 3:35), Laura Hitt wrote:
> Hi Kohei,
> Yes, thank you, that modification is better.
> -Laura
>
>
> -----Original Message-----
>> From: Kohei Kasamatsu [mailto:[email-masked]]
>> Sent: Wednesday, January 29, 2014 5:02 AM
>> To: Laura Hitt; [email-masked]
>> Cc: [email-masked]; [email-masked]
>> Subject: Re: [Cfrg] Fwd: I-D Action: draft-kasamatsu-bncurves-00.txt
>>
>> Hi Laura,
>>
>>
>>> Regarding your statement in Section 6, "The elliptic curve that
>>> supports a bilinear map requires the hardness of solving following
>>> problems, since the security of pairing-based cryptographic primitives
>>> is based on hardness of these problems."  You then list the ECDLP,
>>> ECDHP, BDHP, ECDLP with auxiliary inputs.
>>>
>>> I would be hesitant to say ALL pairing-based cryptographic primitives
>>> are based on the hardness of those problems...perhaps it's true, but
>>> it's conceivable that a pairing-based scheme could be based on another
>>> hard problem, such as solving the isogeny problem or co-gap DH. (See,
>>> for example, Section 6 of "Evaluating Large Degree Isogenies and
>>> Applications to Pairing Based Cryptography" by Broker, Charles,
>>> Lauter, or "Improved algorithm for the isogeny problem for ordinary
>>> elliptic curves" by Galbraith & Stolbunov.)
>>
>> We agree with it.
>> As you say, there are pairing-based cryptographic primitives based on the
>> hardness of different problems from these described in our draft.
>>
>> We would like to change
>> "The elliptic curve that supports a bilinear map requires the hardness of
>> solving following problems, since the security of pairing-based
>> cryptographic primitives is based on hardness of these problems."
>> to
>> "Pairing-based cryptographic primitives are often based on the hardness of
>> the following problems, so when the elliptic curves from this document are
>> used in such schemes, these problems would apply."
>>
>> Does the modification despel the concern?
>>
>> Best,
>> Kohei KASAMATSU
>>
>>
>> (2014/01/24 3:13), Laura Hitt wrote:
>>> Hi Kohei,
>>>
>>> Regarding your statement in Section 6, "The elliptic curve that supports
>> a bilinear map requires the hardness of solving following problems, since
>> the security of pairing-based cryptographic primitives is based on hardness
>> of these problems."  You then list the ECDLP, ECDHP, BDHP, ECDLP with
>> auxiliary inputs.
>>>
>>> I would be hesitant to say ALL pairing-based cryptographic primitives
>>> are based on the hardness of those problems...perhaps it's true, but
>>> it's conceivable that a pairing-based scheme could be based on another
>>> hard problem, such as solving the isogeny problem or co-gap DH. (See,
>>> for example, Section 6 of "Evaluating Large Degree Isogenies and
>>> Applications to Pairing Based Cryptography" by Broker, Charles,
>>> Lauter, or "Improved algorithm for the isogeny problem for ordinary
>>> elliptic curves" by Galbraith & Stolbunov.)
>>>
>>> Best,
>>> Laura
>>>
>>> -----Original Message-----
>>> From: Cfrg [mailto:[email-masked]] On Behalf Of Kohei Kasamatsu
>>> Sent: Wednesday, January 22, 2014 6:04 PM
>>> To: [email-masked]
>>> Cc: [email-masked]; [email-masked]
>>> Subject: [Cfrg] Fwd: I-D Action: draft-kasamatsu-bncurves-00.txt
>>>
>>> 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: [email-masked]
>>> Reply-To: [email-masked]
>>> To: [email-masked]
>>>
>>>
>>> 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
>>> [email-masked]
>>> 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
>>> [email-masked]
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>>
>>>
>>
>>
>> --
>> Kohei KASAMATSU
>>
>> NTT Software Corporation
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
Kohei KASAMATSU

NTT Software Corporation