| Network Working Group | K. Kasamatsu |
| Internet-Draft | S. Kanno |
| Intended status: Informational | NTT Software Corporation |
| Expires: July 13, 2014 | T. Kobayashi |
| Y. Kawahara | |
| NTT | |
| January 09, 2014 |
Barreto-Naehrig Curves
draft-kasamatsu-bncurves-00
Elliptic curves with pairing are useful tools for constructing cryptographic primitives. In this memo, we specify domain parameters of Barreto-Naehrig curve (BN-curve) [BN2006]. 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 [BGMORT2010] [AKLGL2011] 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[ISO15946-5]. 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[Aranha13].
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on July 13, 2014.
Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Elliptic curves with a special map called a pairing or bilinear map allows cryptographic primitives to achieve functions or efficiency which cannot be realized by conventional mathmatical tools. There are identity-based encryption (IBE), attribute-based encryption (ABE), ZSS signature, broadcast encryption (BE) as examples of these primitives. IBE realizes powerful management of public key by allowing us to use a trusted identifier as a public key. ABE provides a rich decryption condition based on boolean functions and attributes corresponding to a secret key or a ciphertext. The ZSS signature gives shorter size of signature than that of ECDSA. BE provides an efficient encryption procedure in a broadcast setting.
Some of these cryptographic schemes based on elliptic curves with pairing were proposed in the IETF (e.g. [RFC5091], [RFC6508], and [I-D.draft-hitt-zssbn-02]) and used in some protocols (e.g. [RFC5409], [RFC6267], [RFC6507], [RFC6509], and [RFC6539]). These cryptographic primitives will be used actively more in the IETF due to their functions or efficiency.
We need to choose an appropriate type of elliptic curves and parameters for the pairing-based cryptographic schemes, because the choice has great impact on security and efficiency of these schemes. However, an RFC on elliptic curves with pairings has not yet been provided in the IETF.
In this memo, we specify domain parameters of Barreto-Naehrig curve (BN-curve) [BN2006]. The BN-curve allows us to achieve high security and efficiency with pairings due to an optimum embedding degree. This memo specifies domain parameters of two 254-bit BN-curves ([BGMORT2010] and [AKLGL2011]) because of these efficiencies. These BN-curves are known as efficient curves in academia and particularly provide efficient pairing which is generally slowest operation in pairing-based cryptography. There are optimized source codes of ([BGMORT2010] and [AKLGL2011]) as open source softwares ([TEPLA] and [relic]), respectively. Furthermore, this memo specifies domain parameters of 224, 256, 384, and 512-bit curves which are compliant with ISO document [ISO15946-5] and organizes differences between types of elliptic curves specified in ISO document and used in open source softwares, which are called M-type and D-type respectively [Aranha13].
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this memo are to be interpreted as described in [RFC2119].
In this section, we introduce the defintion of elliptic curve and bilinear map, notation used in this memo.
Throughout this memo, let p > 3 be a prime and F_p be a finite field. The curve defined by the following equation E is called elliptic curve.
E : y^2 = x^3 + A*x + B such that A, B are in F_p, 4 * A^3 + 27 * B^2 != 0 mod p
Solutions (x,y) for an elliptic curve E, as well as the point at infinity, are called F_p-rational points. The additive group is constructed by a well-defined operation in the set of F_p-rational points. Typically, the cyclic additive group with prime order q and base point G in E(F_p) is used for the cryptographic applications. Furthermore, we define terminology used in this memo as follows.
Let G_1 be an additive group of prime order p and let G_2 and G_T be additive and multiplicative groups, respectively, of the same order. Let P, Q be generators of G_1, G_2 respectively. We say that (G_1, G_2, G_T) are asymmetric bilinear map groups if there exists a bilinear map e: (G_1, G_2) -> G_T satisfying the following properties:
For BN-curves, G_1 is a q-order cyclic subgroup of E(F_p) and G_2 is a subgroup of E(F_{p^k}), where k is the embedding degree of the curve. The group G_T is the set of q-th roots of unity in the finite field F_{p^k}.
In this section, this memo specifies the domain parameters for two 254-bit elliptic curves which allow us to efficiently compute the operation of a pairing at high levels of security and domain parameters for 224, 256, 384, and 512-bit elliptic curves which are compliant with the ISO document [ISO15946-5].
Here, we define notations for specifying domain parameters and explain types of pairing friendly curves.
Domain parameters of the elliptic curve E(F_p) and E(F_{p^12}) are needed for computation of the pairing. Barreto and Naehrig proposed a method of point and pairing compression by using output of a map I from a sextic twist E'(F_{p^2}) to E(F_{p^12}) instead of E(F_{p^12}). Generally, this method is used with BN-curves. Hence, this memo follows the method. For the details of the method, refer to [BN2006].
The pairing friendly curves are classified two types, which are called D-type and M-type respectively [Aranha13]. The D-type sextic twist curve is defined by equation y'^2 = x'^3 + b/s when elliptic curve E(F_p) is let to be y^2 = x^3 + b and represent of F_{p^12} is let to be F_{p^2}[u]/(u^6 - s), where s is in F_{p^2}^*. Let z be a root of u^6 - s, where z is in F_{p^12}. The corresponding map I: E'(F_{p^2}) -> E(F_{p^12}) is (x', y') -> (z^2 * x', z^3 * y').
The M-type sextic twist curve is defined by equation y'^2 = x'^3 + b * s when elliptic curve E(F_p) is let to be y^2 = x^3 + b and represent of F_{p^12} is let to be F_{p^2}[u]/(u^6 - s), where s is in F_{p^2}^*. The corresponding map I: E'(F_{p^2}) -> E(F_{p^12}) is (x', y') -> (x' * s^{-1} * z^4, y' * s^{-1} * z^3), with z^6 = s.
These domain parameters are described in the following way.
For elliptic curve E
For twist curve E'
In this section, this memo specifies the domain parameters for two 254-bit elliptic curves which are more efficient than parameters of ISO document with D-type.
Here, we describe the domain parameters for 254-bit elliptic curve[BGMORT2010] with D-type.
The domain parameters described in this subsection are defined by Elliptic curve E(F_p) : y^2 = x^3 + 5 and sextic twist E'(F_{p^2}) : x'^3 + 5/s = x'^3 - u, where F_{p^2} = F_{p}[u]/(u^2 + 5), F_{p^6} = F_{p^2}[v]/(v^3 - u), F_{p^12} = F_{p^6}[w]/(w^2 - v), s = - 5/u. We describe domain parameters of elliptic curves E and E'. For the details of these parameters, refer to [BGMORT2010].
Here, we describe the domain parameters for 254-bit elliptic curve [AKLGL2011] with D-type.
The domain parameters described in this subsection are defined by elliptic curve E(F_p) : y^2 = x^3 + 2 and sextic twist E'(F_{p^2}) : x'^3 + 2/s = x'^3 + 1 - u, where ,F_{p^2} = F_p [u]/(u^2 + 1), F_{p^6} = F_{p^2} [v]/(v^3 - (1+u)), F_{p^12} = F_{p^6} [w]/(w^2 - v), 1/s = 1/(1 + u). We describes domain parameters of elliptic curves E and E'. For the details of these parameters, refer to [AKLGL2011].
Here, we describe the domain parameters for 224, 256, 384, and 512-bit elliptic curves which are compliant with the ISO document and are based on M-type. The domain parameters described in below subsections are defined by Elliptic curve E(F_p): y^2 = x^3 + 3 and sextic twist E'(F_{p^2}): y'^2 = x'^3 + 3 * s, where F_{p^2} = F_p[X]/(X^2 + 1), F_{p^12} = F_{p^2}[X]/(X^6 - s), s = 1 + X. We describe domain parameters of elliptic curves E. Detailed information on these domain parameters is given in [ISO15946-5].
Although ISO document is based on M-type, open source softwares are often based on D-type. We need to be aware of the differences. Hence we also describe elliptic curve with D-type based on ISO document. The elliptic curve E(F_p) is defined by equation y^2 = x^3 + 3 and the sextic twist E'(F_{p^2}) is defined by y'^2 = x'^3 + 3/s, where F_{p^2} = F_p[X]/(X^2 + 1), F_{p^12} = F_{p^2}[X]/(X^6 - s), 1/s = -8 + 8 * i, i = X^2 + 1. Detailed information on these domain parameters is given in [BN2006].
We need to define the following object identifiers. Which organization is suitable for the allotment of these object identifiers?
Elliptic curves which are specified in this memo have hardness of the problems below and enough security margin against the attacks below.
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. (For details of problems, refer to section 2 of [Cheon06].)
Algorithms to efficiently solve the problems above, aside from special cases, are unknown. When choosing elliptic curve domain parameters we need to consider the Pollard-rho algorithm [Pollard78] and Menezes-Okamoto-Vanstone algorithm [MOV93] as generic attacks against ECDLP. The Pollard-rho algorithm is believed to have the best performance against ECDLP at present. However, it is an exponential time algorithm. Menezes-Okamoto-Vanstone algorithm converts ECDLP into the discrete logarithm problem in a finite field F_{p^k}^*, the codomain of the bilinear map, where k is embedding number. This is a subexponential time algorithm.
The Smart, Semaev, and Sato-Araki algorithm [SA98], and Cheon algorithm [Cheon06] are main algorithms which improve efficiency in specific cases. The Smart-Semaev algorithm and Sato-Araki algorithm are polynotmial time algorithms against the ECDLP in the case where #E(F_{p}) equals to p. These algorithms are independently proposed. Cheon algorithm [Cheon06] is against the ECDLP with auxiliary inputs. It is prevented by satisfy the following condition, where n is order.
Table 1 shows the security level of elliptic curves described in this memo ([BGMORT2010], [AKLGL2011]). Schemes based on the elliptic curves must be combined with cryptographic primitives which have similar or greater security level than the scheme.
| Curve-ID | Security Level (bits) |
--------------------------------------
| Fp224BN | 112 |
| Fp254BNa | 128 |
| Fp254BNb | 128 |
| Fp256BN | 128 |
| Fp384BN | 128 |
| Fp512BN | 128 |
Table 1: security level of elliptic curve specified in this memo
This memo was inspired by the content and structure of [RFC5639].
NOTE TO RFC EDITOR: Please remove this section in before final RFC publication.
| [1] | Beuchat, J. L., Gonzalez-Diaz, J. E., Mitsunari, S., Okamoto, E., Rodriguez-Henriquez, F. and T. Teruya, "High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves", Proceedings Lecture notes in computer sciences; Pairing-Based Cryptography --Pairing2010, 2010. |
| [2] | Aranha, D. L., Karabina, K., Longa, P., Gebotys, C. H., Rodriguez-Henriquez, F. and J. Lopez, "Faster Explicit Formulas for Computing Pairings over Ordinary Curves", Proceedings Lecture notes in computer sciences; EUROCRYPT --EUROCRYPT2011, 2011. |
| [3] | International Organization for Standardization, "Information Technology - Security Techniques -- Cryptographic techniques based on elliptic curves . Part 5: Elliptic curve generation ", ISO/IEC 15946-5, 2009. |
| [4] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. |