Network Working Group A. Kato
Internet-Draft NTT TechnoCross Corporation
Intended status: Experimental T. Kobayashi
Expires: September 19, 2018 Y. Kawahara
T. Kim
T. Saito
NTT
March 18, 2018

The threat of Pairing based cryptographic protocols.
draft-kato-threat-pairing-00

Abstract

Pairing is a special map from two elliptic curves that called Pairing-friendly curves to a finite field and is useful mathematical tools for constructing cryptographic primitives.

At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve algorithm for the discrete logarithm problem in a finite field. The security of pairing-based cryptography is based on the difficulty in solving the DLP. Hence, it has become necessary to shift the parameters that the DLP is computationally infeasible against the efficient number field sieve algorithms.

This memo introduce Optimal Ate Pairing and two pairing-friendly curves with parameters of pairing against efficient number field sieve algorithms.

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 https://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 19, 2018.

Copyright Notice

Copyright (c) 2018 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 (https://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 curves that called Pairing friendly 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[14] 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.

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 some open source softwares ([7], [8], and [9]) are implemented by Optimal Ate Pairing which is an improvement of Ate Pairing with 254-bit prime order Barreto and Naehrig curve.

At CRYPTO 2016, Kim and Barbulescu proposed an efficient number field sieve(NSF) algorithm for the discrete logarithm problem in a finite field[11]. The security of pairing-based cryptography is based on the difficulty in solving the DLP. Hence, it has become necessary to shift the parameters that the DLP is computationally infeasible against the efficient NSF algorithms.

This memo introduce Optimal Ate Pairing [2] for two PFCs to be able to shift the parameters. 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 BLS-curves Section 3 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)

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

2. Preliminaries

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

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

2.2. Bilinear Map

Let G_1 be an additive group of prime order r and let G_2 and G_3 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_3) are asymmetric bilinear map groups if there exists a bilinear map e: (G_1, G_2) -> G_3 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.

3. Pairing-friend curves and Domain Parameter Specification

In this section, this memo specifies the domain parameters for 128-bit and 256-bit secure elliptic curves which allow us to efficiently compute the operation of a pairing at appropriate levels of security.

We introduce 462-bit Barreto Naehrig (BN462)[13] curve as 128-bit secure elliptic curve and 581-bit Barreto Lynn Scott (BLS48)[12]. curve as 256-bit secure elliptic curve.

3.1. Notation for Domain Parameters

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

The elliptic curves E over F_p satisfy following equation.

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

These domain parameters are described in the following way.

For the elliptic curve E(F_p) on BN462

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

For F_{p^12}^* on BN462

For the elliptic curve E(F_p) on BLS48

For twisted curve E'(F_{p^8}) on BLS48

For F_{p^48}^* on BLS48

For the definition of the pairing parameter

3.2. Efficient Domain Parameters for BN462

This section specifies the domain parameters for four 128-bit secure elliptic curves BN462.

3.2.1. Domain Parameters by Beuchat et al.

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 + 2 - u, where F_{p^2} = F_p[u]/(u^2 + 1), 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. 

   Pairing-Param-ID: Fp462BN = {
       G1-Curve-ID: Fp462nBN
       G2-Curve-ID: Fp462n2BN
       G3-Field-ID: Fp462n12BN
   }

3.3. Efficient Domain Parameters for BLS48

This section specifies the domain parameters for four 256-bit secure elliptic curves BLS48.

3.3.1. Domain Parameters by Kiyomura et al.

The domain parameters described in this subsection are defined by elliptic curve E(F_p) : y^2 = x^3 + 1 and following tower structures E'(F_{p^8}) : y^2 = x^3 -1/w, where F_{p^2} = F_p[u]/(u^2 + 1), F_{p^4} = F_{p^2}[v]/(v^2 + u + 1), F_{p^8} = F_{p^4}[w]/(w^2 + v), F_{p^24} = F_{p^8}[z]/(z^3 + w), f_{p^48} = f_{p^24}[s]/(s^2 + z).

The polynomials p(x), r(x) and t(x) satisfies CM equation D = 3, n(x) = p(x) + 1 - t(X), 4p(x) - t(x)^2 = Df(x)^2.

p(x) = (x - 1)^2(x^16 - x^8 + 1)/3 + x.

r(x) = x^16 - x^8 + 1.

t(x) = x + 1.

x_0 is specific parameter in CM equation.

x_0 = -1 + 2^7 - 2^20 - 2^30 - 2^32.

   Pairing-Param-ID: Fp581BLS48 = {
       G1-Curve-ID: Fp581BLS48n
       G2-Curve-ID: Fp581BLS48n8
       G3-Field-ID: Fp581BLS48n48
   }

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 the 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 choose 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. Algorithm Identifiers

(TBD)

6. Security Considerations

The pairing is a map from two elliptic curves G1 and G2 to a multiplicative subgroup of a finite field.

Typically, G1 (respectively G2) is a cyclic subgroup in E(F_p) (respectively E'(F_{p^{k/d})) of prime order r, where k is the embedding degree and d is the degree of the twist. The group G3 is a set of r-th roots of unity in F_{p^k}^*. In this section, G_1', G_2' and G_3' denote E(F_p), E'(F_{p^{k/d}}) and F_{p^k}^* respectively.

Pairing-based cryptographic primitives are often based on the hardness of the following problems.

On the side of G1' and G2', the best known algorithm (for instance, Pollard-rho algorithm [10]) to solve ECDLP has a running time of O(sqrt(r)), which is exponential in r, where r is the order of the target group. Thus, for a security parameter l, one should set r so that log_2(r)>2*l.

On the side of G3', one has more efficient algorithm based on Number Field Sieve methods (cite Gordon93 paper here, if you want). The complexity of the NFS (including its variants) is subexponential in the size of the finite field and is independent from the size of the subgroup order r. Recall the classical L-notation, L(q, a, c)= exp( (c+o(1))*log(q)^a * log(log(q))^(1-a) ). Before 2016, the best known algorithm for FFDLP has had a running time of L(p^k, 1/3, 1.92) and the parameters of currently used pairings are derived from the above value. At CRYPTO2016, however, Kim and Barbulescu proposed a new variant of the NFS method that drastically reduces the complexity of solving FFDLP from L(p^k, 1/3, 1.92) to L(p^k, 1/3, 1.53) in the best case[11]. For instance, Barbulescu estimates that the security of the pairing over BN curve, which was believed to have 128-bit security, drops to approximately 100-bit security. Hence, it has become necessary to revise the bit length of q=p^k so that the FFDLP over F_{p^k} is computationally infeasible against this new efficient NFS algorithm.

G_3' 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 implementers should necessary to ensure adequate security level for both of problems.

6.1. 128-bit Secure PFC

Barreto and Naehrig showed how to construct pairing-friendly curves[13]. We have chosen 462-bit prime order curve and described in Section 3.

6.2. 256-bit Secure PFC

Five 256-bit secure domain parameters have been proposed by Kiyomura[12]. We have chosen the BLS48 as 256-bit secure PFC and described in Section 3.

7. Acknowledgements

(TBD)

8. Change log

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

9. References

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

9.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] "University of Tsukuba Elliptic Curve and Pairing Library", 2013.
[8] Aranha, D. and C. Gouv, "RELIC is an Efficient LIbrary for Cryptography", 2013.
[9] Scott, M., "The MIRACL IoT Multi-Lingual Crypto Library", 2015.
[10] Pollard, J., "Monte Carlo Methods for Index Computation ( mod p)", Proceedings Mathematics of Computation, Vol.32, 1978.
[11] Kim, T. and R. Barbulescu, "Extended tower number field sieve: a new complexity for the medium prime case.", CRYPTO 2016 LNCS, vol. 9814, pp. 543.571, 2016.
[12] Kiyomura, Y., Inoue, A., Kawahara, Y., Yasuda, M., Takagi, T. and T. Kobayashi, "Secure and Efficient Pairing at 256-Bit Security Level", ACNS 2017 LNCS, vol. 10355, pp. 59.79, 2017, 2017.
[13] Barreto, Paulo. and Michael. Naehrig, "Pairing-Friendly Elliptic Curves of Prime Order", Selected Areas in Cryptography-SAC 2005. volume 3897 of Lecture Notes in Computer Science, pages 319-331, 2006.
[14] "ISO/IEC 14888-3:2016", ISO/IEC Information technology -- Security techniques -- Digital signatures with appendix -- Part 3: Discrete logarithm based mechanisms, 2016.

Appendix A. Test Vectors of Optimal Ate Pairing

In this section, we specify test vectors of Optimal Ate Pairing over BN-curve and BLS-curve which are specified by Section 3 in the following way.

Parameter:

Input:

Output:

(TBD)

Authors' Addresses

Akihiro Kato NTT TechnoCross Corporation EMail: kato.akihiro-at-po.ntt-tx.co.jp
Tetsutaro Kobayashi NTT EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp
Yuto Kawahara NTT EMail: kawahara.yuto-at-lab.ntt.co.jp
Teachan Kim NTT EMail: taechan.kim-at-lab.ntt.co.jp
Tsunekazu Saito NTT EMail: saito.tsunekazu-at-lab.ntt.co.jp