| 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 |
Optimal Ate Pairing
draft-kato-optimal-ate-pairings-01
Pairing is a special map from two elliptic curve that called Pairing-friend curves to a finite field and is useful mathematical tools for constructing cryptographic primitives. It allows us to construct powerful primitives. (e.g. [3] and [4])
There are some types of pairing and its choice has an impact on the performance of the primitive. For example, Tate Pairing [3] and Ate Pairing [4] are specified in IETF. This memo focuses on Optimal Ate Pairing [2] which is an improvement of Ate Pairing.
This memo defines Optimal Ate Pairing for any pairing-friendly curve. We can obtain concrete algorithm by deciding parameters and building blocks based on the form of a curve and the description in this memo. It enables us to reduce the cost for specifying Optimal Ate Pairing over additional curves. Furthermore, this memo provides concrete algorithm for Optimal Ate Pairing over BN-curves [7] and its test vectors.
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.
Copyright (c) 2016 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.
Pairing is a special map from two elliptic curve that called Pairing-friend curves (PFCs) to a finite field and is useful mathematical tools for constructing cryptographic primitives. It allows us to construct powerful primitives like Identity-Based Encryption (IBE) [5] and Functional Encryption (FE) [6]. The IBE and FE provide a rich decryption condition. Some Pairing-Based Cryptography is specified in IETF. (e.g. [3] and [4])
There are some types of pairing and its choice has an impact on the performance of the primitive. For example, primitives by using Tate Pairing [3] and Ate Pairing [4] are specified in IETF. This memo focuses on Optimal Ate Pairing which is an improvement of Ate Pairing. Optimal Ate Pairing allows us to construct Pairing-Based Cryptography with high performance and is implemented in some open source softwares. ([8], [9], and [10])
This memo defines Optimal Ate Pairing [2] for any PFC. We can obtain concrete algorithm by deciding parameters and two building blocks based on the form of a curve. It enables us to reduce the cost for describing the body of Optimal Ate Pairing when Optimal Ate Pairing is specified over additional curves in IETF. Furthermore, this memo provides concrete algorithm for Optimal Ate Pairing over BN-curves [7] and its test vectors. This memo is expected to use by combining Optimal Ate Pairing with a suitable PFC for a primitive in order to realize same functional structure of ECDSA and ECDH. (i.e. DSA over elliptic curve and DH over elliptic curve)
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 [1].
In this section, we introduce the definition of elliptic curve and bilinear map, notation used in this memo.
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.
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:
This section specifies Optimal Ate Pairing e for c_0, ..., c_l and s_i = sum_{j=i}^l c_j * q^j with following conditions
Section 4.1 shows a guide to decide these parameters c_0, ..., c_l. Optimal Ate Pairing is specified below and Miller Loop f which are its building blocks are introduced in Section 4.2. Straight Line Function l which is building blocks of Optimal Ate Pairing and Miller Loop are defined in Section 4.3. Section 4.3 only show the definitions because its descriptions are based on the form (of the PFC?). Practically, concrete algorithms need to be specified for a form of PFC.
Input:
Output:
Method:
end for
end for
This subsection shows a guide for decision on parameters c_0, ..., c_l for Optimal Ate Pairing. According to [2], a way is to choice coefficients of short vector of the following lattice L with a minimal number of coefficients as parameters c_0, ..., c_l.
L = (v_1, ..., v_phi(k)) where
In this subsection, we specify Miller Loop f which is building block of Optimal Ate Pairing.
Input:
Output:
Method:
end if
end for
Straight Line Function l_{Q, Q'}(P) is calculated by a point P for linear equation defined as a line l though points Q, Q'. Note that Straight Line Function l_{Q, Q'}(P) is calculated by a point P for linear equation defined as a tangent line to an elliptic curve E at a point Q of E on condition that Q = Q'. The function is used for Optimal Ate Pairing in Section 4 and Miller Loop in Section 4.2
In this section, we specify Optimal Ate Pairing over BN-curves [7]. BN-curves define over a finite field F_p, and have embedding degree k = 12, r(t) = 36 * t^4 + 36 * t^3 + 18 * t^2 + 6 * t + 1, and p(t) = 36 * t^4 + 36 * t^3 + 24 * t^2 + 6 * t + 1, where t is the specific integer in [7].
The extension fields are defined by following:
The constants e3, e6 and e6 which are varied by G_T are defined in [7].
Hence parameters for Optimal Ate Pairing over D-Type twisted curve are following by the method in Section 4.1:
These short vectors are specified in section 4. A of [2].
Algorithm of Optimal Ate Pairing by Miller Loop in Section 4.2 based on building blocks specified in Section 5.2 and Section 5.3 and Straight Line Function f in Section 5.1 over BN-curves is as following:
Input:
Output:
Method:
This subsection shows an operation of Straight Line Function over BN-curves for Optimal Ate Pairing.
Input:
Output:
Method:
This subsection shows an operation of Doubling Step of Miller Loop over BN-curves. (i.e. operation of method 4-(A) in Section 4.2 over BN-curves)
Input:
Output:
Method:
This subsection shows an operation of Addition Step of Miller Loop over BN-curves. (i.e. operation of method 4-(C)-(a) in Section 4.2 over BN-curves)
Input:
Output:
Method:
TBD
The security of cryptographic primitive which is constructed by pairing depends on pairing-friendly curves (PFC). PFC must satisfy computational assumption which the primitive requires at the level of security strength in system when the primitive is constructed by using Optimal Ate Pairing.
TBD
NOTE TO RFC EDITOR: Please remove this section in before final RFC publication.
| [1] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. |
| [2] | Vercauteren, F., "Optimal pairings", Proceedings IEEE Transactions on Information Theory 56(1): 455-461 (2010), 2010. |
T. Unterluggauer and E. Wenger computed the running time of optimal ate paring on an ARM Coretex-M0+ that is small and energy efficient microprocessor [11]. By their result, optimal ate pairing's running time on Coretex-M0+ is 1 sec.
In this section, we specify test vectors of optimal ate pairing over BN-curves which are specified by [7] in the following way.
Parameter:
Input:
Output:
This subsection shows test vector of 254-bit curves by Beuchat et al. [7] and reprints its parameters under 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) as a reference.
Parameter:
Pairing-Param-ID: Beuchat
Input:
Output:
This subsection shows test vector of 254-bit curves by Nogami et al. / Aranha et al. [7] and reprints its parameters under 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) as a reference.
Parameter:
Pairing-Param-ID: Nogami-Aranha
Input:
Output:
This subsection shows test vector of 254-bit curves by Scott [7] and reprints its parameters under 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) as a reference.
Parameter:
Pairing-Param-ID: Scott
Input:
Output:
This subsection shows test vector of 254-bit curves by BCMNPZ [7] and reprints its parameters under 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) as a reference.
Parameter:
Pairing-Param-ID: BCMNPZ
Input:
Output: