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

Abstract

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.

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.

Copyright Notice

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.


Table of Contents

1. Introduction

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)

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

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.

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.

4. Optimal Ate Pairing

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

  1. c_l is not 0
  2. r is a divisor of s_0
  3. r^2 is not a divisor of s_0
  4. r does not divide s_0 * k * q^{k-1} - (q^k - 1)/r * sum_{i=0}^l i * c_i * q^{i - 1}

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:

  1. f = 1
  2. ln = 1
  3. for i = 0 to l

    end for

  4. for i = 0 to l - 1

    end for

  5. return (f * ln)^{(q^k - 1)/r}

4.1. Guide for Decision on Parameters for Optimal Ate Pairing

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

4.2. Miller Loop

In this subsection, we specify Miller Loop f which is building block of Optimal Ate Pairing.

Input:

Output:

Method:

  1. compute s_0, ..., s_L such that |s| = sum_{j=0}^L s_j * 2^j with s_j is in {0, 1} and s_L = 1
  2. T = Q
  3. f = 1
  4. for j = L - 1 down to 0

    end for

  5. if s < 0, then f = f^{-1}
  6. return f

4.3. Straight Line Function

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

5. Optimal Ate Pairing over BN-curves

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:

  1. l = 3
  2. c_0 = 6 * t + 2
  3. c_1 = 1
  4. c_2 = -1
  5. c_3 = 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:

  1. f_1 = f_{c_0, Q}(P)
  2. l_1 = l_{[p^3]Q}, - [p^2]Q}(P)
  3. l_2 = l_{[p^3]Q - [p^2]Q, [p]Q}(P)
  4. l_3 = l_{[p]Q - [p^2]Q + [p^3]Q, [6 * t + 2]Q}
  5. return (f_1 * l_1 * l_2 * l_3)^{(p^k - 1)/r}

5.1. Straight Line Function over BN-curves

This subsection shows an operation of Straight Line Function over BN-curves for Optimal Ate Pairing.

Input:

Output:

Method:

  1. If Q != +- Q'

  2. If Q = Q'

  3. If Q = -Q'

  4. return ln

5.2. Doubling Step of Miller Loop over BN-Curves

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:

  1. lambda = (3 * x_1^2)/(2 * y_1)
  2. x_3 = lambda^2 - 2 * x_1
  3. y_3 = lambda * (x_1 - x_3) - y_1
  4. t0 = -lambda * x
  5. t1 = lambda * x_1 - y_1
  6. ln = y + t0 w + t1 w^3
  7. return ln and T

5.3. Addition Step of Miller Loop over BN-Curves

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:

  1. lambda = (y_2 - y_1)/(x_2 - x_1)
  2. x_3 = lambda^2 - x_1 - x_2
  3. y_3 = lambda * (x_1 - x_3) - y_1
  4. t0 = -lambda * x
  5. t1 = lambda * x_1 - y_1
  6. ln = y + t0 w + t1 w^3
  7. return ln and T

6. Algorithm Identifiers

TBD

7. Security Considerations

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.

8. Acknowledgements

TBD

9. Change log

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

10. References

10.1. Normative References

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

10.2. Informative References

, "
[3] Boyen, X. and l. Martin, "Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems", RFC 5091, December 2007.
[4] Hitt, L., "ZSS Short Signature Scheme for Supersingular and BN Curves", Internet-Draft draft-irtf-cfrg-zss-02, 2013.
[5] Boneh, D. and M. Franklin, "Identity-based encryption from the Weil pairing", Proceedings Lecture notes in computer sciences; CRYPTO --CRYPTO2001, 2001.
[6] Okamoto, T. and K. Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption", Proceedings Lecture notes in computer sciences; CRYPTO --CRYPTO2011, 2010.
[7] Kasamatsu, K., Kanno, S., Kobayashi, T. and Y. Kawahara, Barreto-Naehrig Curves", Internet-Draft draft-kasamatsu-bncurves-02, 2015.
[8]University of Tsukuba Elliptic Curve and Pairing Library", 2013.
[9] Aranha, D. and C. Gouv, "RELIC is an Efficient LIbrary for Cryptography", 2013.
[10] Scott, M., "The MIRACL IoT Multi-Lingual Crypto Library", 2015.
[11] Unterluggauer, T. and E. Wenger, "Efficient Pairings and ECC for Embedded Systems", 2014.

Appendix A. Perfomance

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.

Appendix B. Test Vectors of Optimal Ate Pairing over BN-curves

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:

B.1. 254-Bit-Curves by Beuchat et al.

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:

B.2. 254-Bit-Curves by Nogami et al. / Aranha et al.

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:

B.3. 254-Bit-Curves by Scott

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:

B.4. 254-Bit-Curves by BCMNPZ

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:

Authors' Addresses

Akihiro Kato NTT Software Corporation EMail: kato.akihiro-at-po.ntts.co.jp
Michael Scott CertiVox EMail: mike.scott-at-certivox.com
Tetsutaro Kobayashi NTT EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp
Yuto Kawahara NTT EMail: kawahara.yuto-at-lab.ntt.co.jp