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

From: Kohei Kasamatsu <[email-masked]>
Date: Thu, 23 Jan 2014 09:04:12 +0900

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

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 22 Jan 2014 16:46:38 -0800

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 <[email-masked]> wrote:

> 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.
> 
> A New Internet-Draft is available from the on-line Internet-Drafts directories.
> 
> 
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Kohei Kasamatsu <[email-masked]>
Date: Wed, 29 Jan 2014 20:01:49 +0900

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

-- 
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: Wed, 29 Jan 2014 20:02:21 +0900

Hi Laura,

Thank you for your comments.

> 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.
>

-- 
Kohei KASAMATSU

NTT Software Corporation

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 29 Jan 2014 10:31:50 -0800

On Jan 29, 2014, at 3:01 AM, Kohei Kasamatsu <[email-masked]> wrote:

> 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