Network Working Group A. Kato Internet-Draft NTT Software Corporation Intended status: Informational M. Scott Expires: September 25, 2016 CertiVox T. Kobayashi Y. Kawahara NTT March 24, 2016

Barreto-Naehrig Curves
draft-kasamatsu-bncurves-02

Abstract

Elliptic curves with pairings are useful tools for constructing cryptographic primitives. In this memo, we specify domain parameters of Barreto-Naehrig curves (BN-curves) [8]. 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 four 254-bit BN-curves [1] [2] [5] which allow us to obtain efficient implementations.

Status of This Memo

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 September 25, 2016.

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.

1.Introduction

Elliptic curves with a special map called a pairing or bilinear map allow cryptographic primitives to achieve functions or efficiency which cannot be realized by conventional mathematical tools. There are identity-based encryption (IBE), attribute-based encryption (ABE), ZSS signature, broadcast encryption (BE) as examples of such primitives. IBE realizes powerful management of public keys 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 a 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 pairings were proposed in the IETF (e.g. [9], [10], and [11]) and used in some protocols (e.g. [12], [13], [14], [15], and [16]). 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 curve 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) [8]. The BN-curve allows us to achieve high security and efficiency with pairings due to an optimum embedding degree for 128-bit security. This memo specifies domain parameters of four 254-bit BN-curves ([1] and [2]) because of these efficiencies ([5]). These BN-curves are known as efficient curves in academia and particularly provide efficient pairing computation which is generally slowest operation in pairing-based cryptography. There are optimized source codes of ([1] and [2]) as open source software ([20] , [21], and [23]), respectively. This memo describes domain parameters of 224, 256, 384, and 512-bit curves which are compliant with ISO document [3] and organizes differences between types of elliptic curves which are compliant with ISO document [3] in Appendix A.

2. Requirements Terminology

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 [4].

3.Preliminaries

In this section, we introduce the definition of elliptic curve and bilinear map, notation used in this memo.

3.1.Elliptic Curve

Throughout this memo, let p > 3 be a prime, q = p^n, and n be a natural number. Also, let F_q be a finite field. The curve defined by the following equation E is called an elliptic curve.

E : y^2 = x^3 + A * x + B such that A, B are in F_q,
4 * A^3 + 27 * B^2 != 0 mod F_q

Solutions (x, y) for an elliptic curve E, as well as the point at infinity, are called F_q-rational points. The additive group is constructed by a well-defined operation in the set of F_q-rational points. Typically, the cyclic additive group with prime order r and the base point G in its group is used for the cryptographic applications. Furthermore, we define terminology used in this memo as follows.

• O_E: the point at infinity over elliptic curve E.
• #E(F_q): number of points on an elliptic curve E over F_q.
• cofactor h: h = #E(F_p)/r.
• embedding degree k: minimum integer k such that r is a divisor of q^k - 1

3.2.Bilinear Map

Let G_1 be an additive group of prime order r 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:

1. Bilinearity: for any S in G_1, for any T in G_2, for any a, b in Z_r, we have the relation e([a]S, [b]T) = e(S, T)^{a * b}.
2. Non-degeneracy: for any T in G_2, e(S, T) = 1 if and only if S = O_E. Similarly, for any S in G_1, e(S, T) = 1 if and only if T = O_E.
3. Computability: for any S in G_1, for any T in G_2, the bilinear map is efficiently computable.

For BN-curves, G_1 is a r-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 r-th roots of unity in the finite field F_{p^k}.

4.Domain Parameter Specification

In this section, this memo specifies the domain parameters for four 254-bit elliptic curves which allow us to efficiently compute the operation of a pairing at high levels of security.

4.1.Notation for Domain Parameters and Types of Sextic Twists

Here, we define notations for specifying domain parameters and explain types of pairing friendly curves.

The BN-curves E over F_p satisfy following equation.

y^2 = x^3 + B for B in F_p

The values p and r are computed from a suitable integer t.

p is a characteristic of a prime field F_p: p = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1.

r is order of group E over F_p: r = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1.

Also, the value b in the constant of the irreducible field polynomial u^2 + b in F_{p^2}.

Domain parameters of the elliptic curve E(F_p) and E(F_{p^12}) are needed for computation of the pairing. In the pairing over BN-curves, we usually use a sextic twist curve group E'(F_{p^2}) and a map I from the sextic twist E'(F_{p^2}) to E(F_{p^12}) instead of E(F_{p^12}). Hence, this memo follows the group and the map. For the details of the group and the map, refer to [8].

The sextic twist curves are classified in two types, which are called D-type and M-type respectively [22]. The D-type sextic twist curve is defined by equation E': y'^2 = x'^3 + B/s when elliptic curve E(F_p) is set to be y^2 = x^3 + B and represent of F_{p^12} is set 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 E': y^2 = x^3 + B * s when elliptic curve E(F_p) is set to be y^2 = x^3 + B and represent of F_{p^12} is set 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.

For the pairing, the group G_1 is defined as the subgroup of order r in E(F_p). Then, the group G_2 is defined as the subgroup of order r in E'(F_{p^2}). The group G_T is subgroup of order r in the multiplicative group F_{p^12}^*. The output of pairing is an element on G_T. The order of F_{p^12}^* can be decomposed into (p^12 - 1) = (p^6 - 1) * (p^2 + 1) * (p^4 - p^2 + 1)/r. Let the cofactor h'' of r on F_{p^12} be h''_1 * h''_2, where h''_1 = (p^4 - p^2 + 1)/r and h''_2 = (p^6 - 1) * (p^2 + 1).

These domain parameters are described in the following way.

For elliptic curve E(F_p)

• G1-Curve-ID is an identifier of the G_1 curve with which the curve can be referenced.
• p_b is a prime specifying a base field F_p.
• B is the coefficient of the equation y^2 = x^3 + B mod p defining E.
• G = (x, y) is the base point, i.e., a point with x and y being its x- and y-coordinates in E, respectively.
• r is the prime order of the group generated by G.
• h is the cofactor of G in E(F_p)

For twisted curve E'(F_{p^2})

• G2-Curve-ID is an identifier of the G_2 curve with which the curve can be referenced.
• p_b is a prime specifying a base field.
• e2 is the constant of an irreducible polynomial specifying extension field F_{p^2} = F_p[u]/(u^2 - e2).
• B' is the coefficient of the equation y'^2 = x'^3 + B' mod F_p^2 defining E'.
• G' = (x', y') is the base point, i.e., a point with x' and y' being its x'- and y'-coordinates in E', respectively.
• r' is the prime order of the group generated by G'.
• h' is the cofactor of r' in #E'(F_{p^2})

For F_{p^12}^*

• GT-Field-ID is an identifier of the F_{p^12}^*.
• p_b is a prime specifying base field.
• r'' is the prime order of the group.
• e2 is the constant of the irreducible polynomial of F_{p^2} = F_p [u]/(u^2 - e2).
• e6 is the constant of the irreducible polynomial of F_{p^6} = F_{p^2}[v]/(v^3 - e6).
• e12 is the constant of the irreducible polynomial of F_{p^12} = F_{p^6}[w]/(w^2 - e12).
• h'' is the cofactor of r in F_{p^12}^* s.t. h'' = h''_1 * h''_2
• h''_1 is the part of cofactor of r in F_{p^12}^* s.t. h''_1 = (p^4 - p^2 + 1)/r
• h''_2 is the part of cofactor of r in F_{p^12}^* s.t. h''_2 = (p^6 - 1) * (p^2 + 1)

For the definition of the pairing parameter

• Pairing-Param-ID is the set of the identifiers G1-Curve-ID, G2-Curve-ID and GT-Field-ID.

4.2.Efficient Domain Parameters for 254-Bit-Curves

This section specifies the domain parameters for four 254-bit elliptic curves. All twisted domain parameters specified in this section are D-type.

4.2.1.Domain Parameters by Beuchat et al.

The domain parameters by Beuchat et al. [1] generated by t = 3fc0100000000000.

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'. The parameter p_b is 1 mod 8. For the details of these parameters, refer to [1].

• G1-Curve-ID: Fp254BNa
• p_b = 0x2370fb049d410fbe4e761a9886e502417d023f40180000017e80600000 000001
• x = 1
• r = 0x2370fb049d410fbe4e761a9886e502411dc1af70120000017e8060000000 0001
• h = 1

• G2-Curve-ID: Fp254n2BNa
• p_b = 0x2370fb049d410fbe4e761a9886e502417d023f40180000017e80600000 000001
• e2 = -5 in F_p
• B' = -u
• x' = 0x19b0bea4afe4c330da93cc3533da38a9f430b471c6f8a536e81962ed967 909b5 + (0xa1cf585585a61c6e9880b1f2a5c539f7d906fff238fa6341e1de1a2 e45c3f72) u
• y' = 0x17abd366ebbd65333e49c711a80a0cf6d24adf1b9b3990eedcc91731384 d2627 + (0x0ee97d6de9902a27d00e952232a78700863bc9aa9be960C32f5bf9f d0a32d345) u
• r' = r
• h' = 0x2370fb049d410fbe4e761a9886e50241dc42cf101e0000017e806000000 00001

• GT-Field-ID: Fp254n12a
• p_b = 0x2370fb049d410fbe4e761a9886e502417d023f40180000017e80600000 000001
• r'' = r
• e2 = -5 in F_p
• e6 = u in F_{p^2}
• e12 = v in F_{p^6}
• h''_1 = 0xade56cf7e1002629c65ca37294ca9149f129ccbb50212575b3d18098 dac4072302eae88c14b40564d9b21719304c9efd7c907850461e1ce3a37da6d40b e2032e03c8c76238b30af10d6da963854a4aca504a90ae0000017e806000000000 01

   Pairing-Param-ID: Beuchat = {
G1-Curve-ID: Fp254BNa
G2-Curve-ID: Fp254n2BNa
GT-Field-ID: Fp254n12a
}

4.2.2.Domain Parameters by Nogami et al. / Aranha et al.

The domain parameters by Nogami et al. [2] generated by t = -0x4080000000000001. Aranha et al. presented an open source library of the pairing using this parameter [2].

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'. The parameter p_b is 3 mod 4. For the details of these parameters, refer to [2].

• G1-Curve-ID: Fp254BNb
• p_b = 0x2523648240000001ba344d80000000086121000000000013a700000000 000013
• B = 2
• x = 0x2523648240000001ba344d80000000086121000000000013a70000000000 0012
• y = 1
• r = 0x2523648240000001ba344d8000000007ff9f800000000010a10000000000 000d
• h = 1

• G2-Curve-ID: Fp254n2BNb
• p_b = 0x2523648240000001ba344d80000000086121000000000013a700000000 000013
• e2 = -1 in F_p
• B' = 1 + (-1) u
• x' = 0x061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c80 3fb2b + (0x0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c 1e7d54cf3) u
• y' = 0x021897a06baf93439a90e096698c822329bd0ae6bdbe09bd19f0e07891c d2b9a + (0x0ebb2b0e7c8b15268f6d4456f5f38d37b09006ffd739c9578a2d1ae c6b3ace9b) u
• r' = r

• GT-Field-ID: Fp254n12b
• p_b = 0x2523648240000001ba344d80000000086121000000000013a700000000 000013
• r'' = r
• e2 = -1 in F_p
• e6 = 1 + u in F_{p^2}
• e12 = v in F_{p^6}
• h''_1 = 0xc816ed457c4f0cbba598fbf85278d6a283736855af2828a32ad1c29a 144223e6281b946847fdfeb69c50d19a04e83b02b9108347fe83011a78b30ec3c0 4f5235bd893d800083e82c022780000099261da2800000006fd671000000000027 0d

   Pairing-Param-ID: Nogami-Aranha = {
G1-Curve-ID: Fp254BNb
G2-Curve-ID: Fp254n2BNb
GT-Field-ID: Fp254n12b
}

4.2.3.Domain Parameters Scott

The domain parameters by Scott generated by t = -0x4000806000004081 [6].

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'. The parameter p_b is 3 mod 4. For the details of these parameters, refer to [2].

• G1-Curve-ID: Fp254BNc
• p_b = 0x240120db6517014efa0bab3696f8d5f06e8a555614f464babe9dbbfeee b4a713
• B = 2
• x = 0x240120db6517014efa0bab3696f8d5f06e8a555614f464babe9dbbfeeeb4 a712
• y = 1
• r = 0x240120db6517014efa0bab3696f8d5f00e88d43492b2cb363a75777e8d30 210d
• h = 1

• G2-Curve-ID: Fp254n2BNc
• p_b = 0x240120db6517014efa0bab3696f8d5f06e8a555614f464babe9dbbfeee b4a713
• e2 = -1 in F_p
• B' = 1 + (-1) u
• r' = r
• x' = 0x0571af2ea9666eb2a53f3fb837172bdd809c03a95c5870f34a8cb340220 bf9c0 + (0x0f71abb712a9e6e12c07b58bc01f2f994c3b5a1531cf96609b838e5 ccf05bc71) u
• h' = 0x240120db6517014efa0bab3696f8d5f0ce8bd6779735fe3f42c6007f503 92d19

• GT-Field-ID: Fp254n12c
• p_b = 0x240120db6517014efa0bab3696f8d5f06e8a555614f464babe9dbbfeee b4a713
• r'' = r
• e2 = -1 in F_p
• e6 = 1 + u in F_{p^2}
• e12 = v in F_{p^6}
• h''_1 = 0xb651238d914d6ec916c6f4c59202389fb75a267e7c7feabf4a5ee9ef 5aa0b588f60d6f5d737b92988f3253f3d3c8aa439f0743d28102d47dc7e0b0ff07 f71e282739c9d5a3236579d81733eaf9269bb184134d7ac2c082e05ea6e634f918 0d

   Pairing-Param-ID: Scott = {
G1-Curve-ID: Fp254BNc
G2-Curve-ID: Fp254n2BNc
GT-Field-ID: Fp254n12c
}

4.2.4.Domain Parameters by BCMNPZ

The domain parameters by BCMNPZ generated by t = -0x4000020100608205 [7].

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'. The parameter p_b is 3 mod 4. For the details of these parameters, refer to [7].

• G1-Curve-ID: Fp254BNd
• y = 1
• B = 2
• h = 1

• G2-Curve-ID: Fp254n2BNd
• e2 = -1 in F_p
• B' = 1 + (-1) u
• r' = r
• y' = 0x02b27f22c2920fee3b4af218b6d92421780a9bdc66155142fecef3af7f5 8e872 + (0x14e9c62a36ebce710810576b5401fdf0b28126ad2d563bf5043be33 47646dfb4) u

• GT-Field-ID: Fp254n12d
• r'' = r
• e2 = -1 in F_p
• e6 = 1 + u in F_{p^2}
• e12 = v in F_{p^6}
• h'' = 0x1d39fc2421c459d1f0de7cde7c1285648918cd045a503063f111e3aaba 83df215962969c6fceb6f999c374d7c0fb36eb380701566be2e2b206368ba4f04e ebcdf9c008c23935547b5a46e37a5f1f6e26745bf3219c8b4456c4fbc261596000 4d5f42547d6b9a867244929fd958b2f962fb35d58f0225a524e4199f3e961c67e9 b1618141cbe93892841e90040854c324d828bcabba01c45b1c8d62829192d22d2f a7281370c28fe7449df33a45af6bf04c8fc54e271bd28c671b5ef06591044fce06 13d7a0fb7a9f4467428dcdf071e85f86bf6097ec6dd14b974aa94a1d189b2227ae 75851160753faac94c2bcb2c15fd5be5e68fc316683ac92cf07b7030c91b25e4dd 40f8a6fc9c128f52b060f4be0c33dd22007c9df38874bf6ce8f21736b6ce5b2d0a 69d802b0efe5d3a05fe0fa939f27bdb66812f89bfef4c3852044c18aa3059d5b63 505ec878753497904916ce2ede9dd267ccd69fcf26c50
• h''_2 = 0x290d9d32167d7406812204488b22639b77897f44694c058dd022c218 16fc3e82f03b87223ac3b8fba7a347184422c7278b0d501d0de0374429d873e7ef 5c86ca749bc6bc55607d2f6dc47fc8fa1abf770d4341041836d6de95ffa72e2cee 6b0ace366bdd8d94be2d4c7c4a4f2312b12932ca02c795a69a53467ce26ae7afb2 f5d99e43aec676bc1564aad101c07a096650986516e4680683384113fcb842d1d4 b6dc261a852b3e85e2b39d159189a82de7794fe53d10feec08ec3521b110b1cfc4 d9d49204f248f9d162489f3bb2c5c0725a1e6da1e0b7df86f8464cc6df13439cd2 5d90d220d3514c1824b5917c5713a224dcd44c8e2c08fbe2e9fc510

   Pairing-Param-ID: BCMNPZ = {
G1-Curve-ID: Fp254BNd
G2-Curve-ID: Fp254n2BNd
GT-Field-ID: Fp254n12d
}

5.Object Identifiers

We need to define the following object identifiers. Which organization is suitable for the allotment of these object identifiers?

• Beuchat OBJECT IDENTIFIER ::= {TBD}
• Nogami-Aranha OBJECT IDENTIFIER ::= {TBD}
• Scott OBJECT IDENTIFIER ::= {TBD}
• BCMNPZ OBJECT IDENTIFIER ::= {TBD}

6.Security Considerations

For above sections, G_1 is a r-order cyclic subgroup of E(F_p) and G_2 is a subgroup of E'(F_{p^2}), where k is the embedding degree of the curve and the group G_T is the set of r-th roots of unity in the finite field F_{p^12}^*. In this section, G_1', G_2' and G_T' imply E(F_p), E'(F_{p^2}) and F_{p^12}^* respectively.

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.

• The elliptic curve discrete logarithm problem in G_1' and G_2' (ECDLP)
• The finite field discrete logarithm problem in G_T' (FFDLP)
• The elliptic curve computational Diffie-Hellman (CDH) problem in G_1' and G_2'
• The elliptic curve computational co-Diffie-Hellman problem in G_1' and G_2'
• The elliptic curve decisional Diffie-Hellman (DDH) problem in G_1'
• The bilinear Diffie-Hellman (BDH) problem

Algorithms to efficiently solve the problems above, aside from special cases, are unknown. Mainly, there are Pollard-rho algorithm [18] against point of an elliptic curve G_1' and G_2', and Number Field Sieve method [17] against G_T' which is output of pairing as generic attacks against elliptic curve with pairing .

G_T' to be larger than G_1' and G_2', because FFDLP can be computed more efficiently than ECDLP in most cases. Security level of schemes based on pairing depends most weak level for each problems. Thus implementors should necessary to ensure adequate security level for both of problems.

Table 1 shows the security level of elliptic curves described in this memo Schemes based on the elliptic curves (i.e. G_1' and G_2') and the finite fields (i.e. G_T') must be combined with cryptographic primitives which have similar or greater security level than the scheme.

security level of elliptic curves and finite field specified in this memo
Pairing-Param-ID Security Level for ECDLP in G_1', G_2' (bits) Security Level for FFDLP in G_T' (bits)
Beuchat 128 128
Nogami-Aranha 128 128
Scott 128 128
BCMNPZ 128 128

6.1. Subgroup Security (OPTIONAL requirement)

For BN-curves, G_1' is cryptographic group of large prime order and cofactor h is always 1. On the other hand, G_2', G_T' are consisted of subgroup of order h' and h'' that are not equal to 1 in addition to subgroup of order r , resp. Thus implementors who provided groups in G_2' and G_T', MUST check element of those groups included in subgroup of order r (see [7]).

The order check of G_T' can be performed by exponentiation of h''_1 and h''_2. The exponentiation of h''_2 can be easily computed by using Frobenius map. Whereas the exponentiation of h''_1 is complicated.

For simplification of the order check which is the smallest prime factor of h' and h''_1 will be greater than r, of element, we define OPTIONAL security G_2-strong and G_T-strong security. G_2-strong and G_T-strong means those order of cryptographic group MUST have the smallest prime factor greater than r. Therefore implementors could not check of order, G_2-strong and G_T-strong cryptographic group will not be insecure

Table 2 shows the G_2, G_T-strong security of parameters described in this memo.

G2, G3-strong security
Pairing-Param-ID Have G_2-Strong? Have G_T-Strong?
Beuchat no no
Nogami-Aranha no no
Scott no yes
BCMNPZ yes yes

7. Acknowledgements

This memo was inspired by the content and structure of [19].

8. Change log

NOTE TO RFC EDITOR: Please remove this section in before final RFC publication.

9.1. Normative References

 [1] Beuchat, J., Gonzalez-Diaz, J., 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., Karabina, K., Longa, P., Gebotys, C., 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. [5] Nogami, Y., Akane, M., Sakemi, Y., Kato, H. and Y. Morikawa, "Integer Variable \chi Based Ate Pairing", Proceedings Pairing 2008, LNCS 5209, pp. 178.191, Springer-Verlag , 2008.

9.2. Informative References

, "
 [6] Scott, M., "Unbalancing Pairing-Based Key Exchange Protocols", ePrint http://eprint.iacr.org/2013/688.pdf, 2013. [7] Barreto, P., Costello, C., Misoczki, R., Naehrig, M., Pereira, G. and G. Zanon, "Subgroup security in pairing-based cryptography", ePrint http://eprint.iacr.org/2015/247.pdf, 2015. [8] Barreto, P. and M. Naehrig, "Pairing-Friendly Elliptic Curves of Prime Order", Proceedings Lecture notes in computer sciences; 3897 in Selected Areas in Cryptgraphy -- SAC2005, 2006. [9] Boyen, X. and L. Martin, "Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems", RFC 5091, December 2007. [10] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)", RFC 6508, February 2012. [11] Hitt, L., "ZSS Short Signature Scheme for Supersingular and BN Curves", Internet-Draft draft-irtf-cfrg-zss-02, 2013. [12] Martin, L. and M. Schertler, "Using the Boneh-Franklin and Boneh-Boyen Identity-Based Encryption Algorithms with the Cryptographic Message Syntax (CMS)", RFC 5409, January 2009. [13] Cakulev, V. and G. Sundaram, "MIKEY-IBAKE: Identity-Based Authenticated Key Exchange (IBAKE) Mode of Key Distribution in Multimedia Internet KEYing (MIKEY)", RFC 6267, June 2011. [14] Groves, M., "Elliptic Curve-Based Certificateless Signatures for Identity-Based Encryption (ECCSI)", RFC 6507, February 2012. [15] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key Encryption in Multimedia Internet KEYing (MIKEY)", RFC 6509, February 2012. [16] Cakulev, V., Sundaram, G. and I. Broustis, "IBAKE: Identity-Based Authenticated Key Exchange", RFC 6539, March 2012. [17] Joux, A., Lercier, R., Smart, P. and F. Vercauteren, "The number field sieve in the medium prime case", Proceedings Lecture notes in computer sciences; 4117 in Comput. Sci. -- CRYPTO2006, 2006. [18] Pollard, J., "Monte Carlo Methods for Index Computation ( mod p)", Proceedings Mathematics of Computation, Vol.32, 1978. [19] Lochter, M. and J. Merkle, Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation", RFC 5639, March 2010. [20] University of Tsukuba Elliptic Curve and Pairing Library", 2013. [21] Aranha, D. and C. Gouv, "RELIC is an Efficient LIbrary for Cryptography", 2013. [22] Aranha, D., Barreto, P., Longa, P. and J. Rocardini, "The Realm of the Pairings", SAC 2013, to appear, 2013. [23] Scott, M., "The MIRACL IoT Multi-Lingual Crypto Library", 2015.

Appendix A.Domain Parameters Based on ISO Document

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 twisted curve. 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[u]/(u^2 + 1), F_{p^12} = F_{p^2}[w]/(w^6 - s), s = 1 + u. We describe domain parameters of elliptic curves E. Detailed information on these domain parameters is given in [3].

A.1.1.Domain Parameters for 224-Bit Curves

• G1-Curve-ID: Fp224BN
• p_b = 0xfffffffffff107288ec29e602c4520db42180823bb907d1287127833
• B = 3
• x = 1
• y = 2
• r = 0xfffffffffff107288ec29e602c4420db4218082b36c2accff76c58ed
• h = 1

A.1.2.Domain Parameters for 256-Bit Curves

• G1-Curve-ID: Fp256BN
• p_b = 0xfffffffffffcf0cd46e5f25eee71a49f0cdc65fb12980a82d3292ddbae d33013
• B = 3
• x = 1
• y = 2
• r = 0xfffffffffffcf0cd46e5f25eee71a49e0cdc65fb1299921af62d536cd10b 500d
• h = 1

A.1.3.Domain Parameters for 384-Bit Curves

• G1-Curve-ID: Fp384BN
• p_b = 0xfffffffffffffffffff2a96823d5920d2a127e3f6fbca024c8fbe29531 892c79534f9d306328261550a7cabd7cccd10b
• B = 3
• x = 1
• y = 2
• r = 0xfffffffffffffffffff2a96823d5920d2a127e3f6fbca023c8fbe2953189 2c795356487d8ac63e4f4db17384341a5775
• h = 1

A.1.4.Domain Parameters for 512-Bit Curves

• G1-Curve-ID: Fp512BN
• p_b = 0xfffffffffffffffffffffffffff9ec7f01c60ba1d8cb5307c0bbe3c111 b0ef455146cf1eacbe98b8e48c65deab236fel916a55ce5f4c6467b4eb280922ad ef33
• B = 3
• x = 1
• y = 2
• r = 0xfffffffffffffffffffffffffff9ec7f01c60ba1d8cb5307c0bbe3c111b0 ef445146cf1eacbe98b8e48c65deab2679a34a10313e04f9a2b406a64a5f519a09 ed
• h = 1

A.1.5. Security of ISO curves

In this section, this memo describes ECDLP on G_1' and G_2', FFDLP on G_T' and subgroup security over G_2' and G_T', for ISO curves.

Table 3 shows the security level of ISO curves.

security level of ISO elliptic curves and finite field specified in this memo
Pairing-Param-ID Security Level for ECDLP in G_1', G_2' (bits) Security Level for FFDLP in G_T' (bits)
ISO-Fp224 112 112
ISO-Fp256 128 128
ISO-Fp384 192 128
ISO-Fp512 256 128

Table 4 shows the G_2, G_T-strong security of ISO curves.

G2, G3-strong security of ISO curves
Pairing-Param-ID Have G_2-Strong? Have G_T-Strong?
ISO-Fp224 no no
ISO-Fp256 no no
ISO-Fp384 no no
ISO-Fp512 no no