Pairing based cryptographic schemes derived on elliptic curves

In the recent years, pairing based cryptographic schemes on elliptic curve have been a very active field of research in cryptography. It has also recently become extremely useful in cryptologic constructions related to these objects. The present paper consists of brief survey on pairing based schemes in cryptography. The survey reviews the pairings mathematically and it includes the topics namely pairing-friendly elliptic curves. It also includes a brief introduction to existing identity-based encryption (IBE) schemes and other cryptographic schemes using pairing technology.

Illustrations explain the paper; charts are replotted from the paper's own table values.

Replotted from source data

↗ Enlarge

n (bits): 80 vs 128 vs 192 vs 256Close ×

Replotted from Table 1 (page 4) of the original paper. Every bar is the paper's own table value.

Open full-size image ↗

Introduction

The concept of pairing in cryptography was first introduced by Weil [27] . Generally pairings map pairs of points on an elliptic curve into the multiplicative group of a finite field. The use of pairings in cryptography has developed at an extraordinary pace since the publication of the paper of Joux [11] . Joux's paper is of great interest to cryptographers, who want to start investigating further applications of pairings. The next two important applications of pairings are the identity-based encryption scheme of Boneh and Franklin [3] and the short signature scheme of Boneh, Lynn and Shacham [4] . Since then, there has been a flurry of activity in the design and analysis of cryptographic protocols using pairings. Pairings have been accepted as an indispensable tool for the protocol designer. There has also been a tremendous amount of work on the realization and efficient implementation of bilinear pairings using the Tate pairing on elliptic curves, hyperelliptic curves, and more general kinds of abelian varieties [10,12,13,15,16,24,25,26] . In the world of elliptic curve cryptography, the pairing was initially considered as negative property. This is because it reduces the discrete logarithm problem on some elliptic curves (e.g. super singular curves) to the discrete logarithm problem in a finite field, thus diminishing the strength and practicability of super singular curves in cryptography. Until a tripartite key agreement protocol proposed by Joux in ANTS 2000 [11] , the pairing for the first time became beneficial and favorable to cryptographic research and applications. Later Boneh and Franklin [3] proposed an identity based encryption scheme based on the modified weilpairing and gave thorough analysis about its properties, security and performance. In next two sections we shall discuss a brief mathematical background of elliptic curve cryptography and pairings. A detail study can be found in [9,26] .

Elliptic Curve Cryptography

The use of elliptic curve cryptography was initially suggested by Koblitz [12] and Miller [16] . , where

Mathematical Background Of Pairings

As we know that every point on an elliptic curve E is one of two types (i) a point of finite order i.e. there exists a positive integer n such that O nP  (ii) a point of infinite order i.e. there exist no such n . The points of first type are known as torsion points.

Thus the set of torsion points P on an elliptic curve E denoted by ] [n E is defined as

iii. There exists an algorithm which computes the map n e efficiently.

The value of the pairing belongs to finite field k q F and the embedding degree k is the least natural number such that ) 1 (  k q is divisible by n . The first property is known as bilinearity while second is called non-degeneracy. This bilinear property has enabled the construction of new cryptographic protocols using pairings. Although pairings exist for every elliptic curve but in practice there are curves whose pairings are not suitable for cryptographic applications. Associated to each elliptic curve, there is a parameter that can be calculated known as the embedding degree k . To implement pairings efficiently in cryptography, we required the value of k to be relatively small, definitely less than 100. However, it has been shown that almost all elliptic curves have very large k . Generally, k is of the same size as q , which is greater than or equal to 160 bits. There are mainly two common ways to find pairing-friendly elliptic curves. The first is to use what are known as super-singular elliptic curves, which always have embedding degree less than or equal to six. The second way is to use a technique called the complex multiplication method to construct certain families of elliptic curves with small embedding degree. There are advantages and drawbacks to each way. All known methods to determine such pairing-friendly curves can be found in [6] .

Pairing Types

Galbraith et al. [8] were the first to identify that all of the potentially desirable properties in a protocol cannot be achieved simultaneously, and therefore classified pairings into certain three types. Although Galbraith et al. [8] originally presented three types of pairings but a fourth type was added soon after by Shacham [22] . There are now four types of pairings in literature ( chapter 4, pp. 58-59 of [5] ) discussed as under: Type-I : The pairing ( 2) is said to be of type I if G G  and there exists no short representations for the elements of 1 G .

Type-II :

The pairing ( 2) is said to be of type II if 2 1 G G  and there exists an efficiently computable homomorphism of 2 G into 1

G but not conversely. In this case no efficient secure hashing to the elements in 2 G is possible.

Type-III :

The pairing (2) is said to be of type II if 2 1 G G  and there exists no efficiently computable homomorphism between 1 G and 2 G .

Type-IV :

The pairing (2) is said to be of type II if 2 1 G G  and there exists an efficiently computable homomorphism of 2 G into 1

G with an efficient secure hashing method to the group elements. This type of pairing is not generally used in protocol designs due to its insufficiency. The pairing types essentially arise from observing the practical implications of choosing 1

G and 2 G in different subgroups of ] [n E . The main factors affecting the classification are the ability to hash and/or randomly sample elements of 2 G i.e. the existence of an isomorphism of 2

G which is often required to make security proofs work and issues concerning storage and efficiency. Pairings on super-singular curves come under type I, while the other types of pairings are defined over ordinary elliptic curves. The pairing of type I is commonly known as symmetric pairing while other types of pairings are called asymmetric pairings. The drawback of type I pairing comes when considering bandwidth and efficiency, as the condition that E be supersingular is highly restrictive when it comes to optimizing the speed of computing pairing.

Selection of Elliptic Curves For Pairings

In this section we discuss some well known methods for generating elliptic curves that are suitable for implementing pairingbased cryptographic protocols. The elliptic curves which are suitable for pairing based cryptography are known as pairing friendly curves. The first example of pairing friendly curve is super-singular curve. Following are the conditions for an elliptic curve to be pairing friendly: i) then the parameters n , q and k must satisfy the following conditions:

i) k must be sufficiently large so that the index-calculus methods for solving the discrete logarithm problem in k q F are infeasible.

ii) k must be sufficiently small so that the arithmetic in k q F can be performed efficiently. iii) n must be sufficiently large so that Pollard's rho method for computing discrete logarithms in an order-n subgroup of ) ( q F E is infeasible.

If we assume n q log log  

, then for efficient arithmetic it is required to have  as least as possible. It is also desired the least value of k for faster computation of pairing. To maintain the equivalent levels of security, we must have the constant value of k  .

Many cryptographers recommend choosing 1   but for some protocols 2   is also recommended. Following table-1 shows the selection of parameters on the elliptic curves for the different levels of security.

Super-singular Elliptic Curves

It is observed that for super-singular elliptic curves, the values of embedding degree k are in the set } 6 , 5 ,

. If E is defined over a prime field q F with 3  q , then we have Proposition 4.1 [24] : Let E be an elliptic curve defined over q F , and let ) ( 1

Ordinary Elliptic Curves

In this section we discussed some well known techniques for generating ordinary elliptic curves for pairing based cryptography. [1,19] ): Let q be a prime number and let t be a non-zero integer satisfying q t 2 

A. Complex Multiplication method (

Then complex multiplication norm equation is given by

where D is the discriminant and square free if t is odd, and

with d positive and square free if t is even. The complex multiplication method is an algorithm for finding an elliptic curve E over

. The running time of complex multiplication method is exponential in q log ; however it is efficient in application if D is comparatively small i.e. . All known techniques for generating ordinary elliptic curves with low embedding degree use the complex multiplication method. [18] ): Miyaji et al. [18] were the first to describe a method for constructing ordinary elliptic curves of low embedding degree. Their method is relying on the following result.

B. MNT method (

Proposition 4.2( [18] ): Let 64  q be a prime number and let E be an ordinary elliptic curve defined over C. Cocks-Pinch method ( [7] ): Cocks and Pinch introduced a new method for constructing elliptic curves for any embedding degree. Their method is based on the following result. Proposition 4.3 [7]

. Then there exists an elliptic curve E defined over q F satisfying the following conditions:

Identity Based Encryption

Identity based encryption (IBE) is similar to classical public key cryptography in that each user has a public key for encryption anda private key for decryption. However, unlike classical public key encryption, where the public key is generated from the private key, IBE allows public keys to be set to the value of a pre-existing identifier, such as an email address. Another difference is that for IBE the individual users cannot generate their own private keys, but must instead download them from a trusted third party known as the private key generator (PKG). Furthermore, in order to encrypt messages, the sender must obtain public system parameters from the PKG. These system parameters are used in combination with the intended recipient's identity string to generate an encrypted message. While the concept of IBE was first proposed by Shamir [23] in 1985, he was only able to provide a method for a conceptually similar, but not nearly as useful, identity-based signature scheme. It was not until 20 years later that a practical scheme for IBE was actually published. The tool that made the Boneh-Franklin [3] scheme possible was bilinear pairings.

Another important IBE scheme is the Boneh-Boyen [2] scheme. The primary advantages are that the Boneh-Boyen scheme does not require the random oracle assumption in its security proof, and that the sender does not have to perform a bilinear pairing operation in order to encrypt a message. This reduced computation for the sender comes at the cost an extra pairing operation for the recipient, although the recipient can use a mathematical trick to compute the key (which is the ratio of the results of two different pairing operations) more efficiently than he or she could by computing the two pairing operations separately. Since this scheme is somewhat more complicated and non-intuitive than the Boneh-Franklin scheme, it will not be described here, even in simplified form. It works on similar principles, and aside from the random oracle assumption, makes similar security assumptions to the Boneh-Franklin scheme. A third important IBE scheme is the Sakai et al. [21] scheme. This scheme has been proven secure in the random-oracle model and has better performance overall than either the Boneh-Franklin or the Boneh-Boyen schemes. It does not require a pairing operation for encryption, and only requires a single pairing computation for decryption. A general advantage of IBE is that it simplifies key management procedures of certificate-based public key infrastructures. IBE also offers interesting features arising from the possibility of encoding additional information into a user's identity. IBE may be seen as an advantage or as a drawback, depending on the situation. There are two main drawbacks to IBE. First, the PKG has a master secret key, which if compromised would allow an attacker to decipher any message from any user. Second, the security of IBE relies on problems that have not been studied as extensively as the problems that underlie more traditional cryptosystems.

Conclusion

As we have seen, pairing-based cryptography has much to offer. Pairing-based schemes, such as IBE, provide special properties which cannot be provided through traditional PKI in a straightforward way. These schemes have received sufficient attention from the cryptographic community and no weakness has been identified. While pairing-based cryptography is still an emerging technology, with active research and development, it is being used in large and small scale applications. Bilinear pairings are also being considered for alternative implementations of available functionalities. These include various authentication schemes, privacy-preserving auctions, privacy-friendly aggregation for the smart grid, network communication resilient to traffic analysis, anonymous credentials, and many more.

Figures and tables from the paper

↗ Enlarge

Figure 1Close ×

Addition and doubling of points on an elliptic curve

Open full-size image ↗

Original paper figureSource PDF · page 2 ↗

Security Levels(bits)	n (bits)	qk	k with 1
80	160	960-1280	6-8
128	256	3000-5000	12-20
192	384	7000-9000	18-24
256	512	14000-18000	28-36

Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.

View original table image

↗ Enlarge

Table 1Close ×

Recommended Security levels for Pairing Groups

Open full-size image ↗

Original paper tableSource PDF · page 4 ↗

1. Atkin A, Morain F. Elliptic curves and primality proving, Mathematics of Computation, 1993; 61:29-68.
2. Boneh D, Boyen X. Secure Identity-based Encryption without Random Oracles, in: Advances in Cryptology-Crypto 2004, Lect. Notes in Comput. Sci. 3152, Springer-Verlag, 2004, 443-459.
3. Boneh D, Franklin M. Identity-based encryption from the Weil pairing, Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, 2139, 213-229. Full version: SIAM Journal on Computing, 2001, 2003; 32:586-615.
4. Boneh D, Lynn B, Shacham H. Short signatures from the Weil pairing, Advances in Cryptology-ASIACRYPT 2001, Lecture Notes in Computer Science, 2248, (2001)514-532. Full version: Journal of Cryptology. 2004; 17:297-319.
5. Freeman D, Scott M, Teske E. A Taxonomy of Pairing-Friendly Elliptic Curves, J Cryptology. 2010; 23(2):224-280.
6. Galbraith SD. Pairings, Chapter IX of book Advances in elliptic curve cryptography edited by I. Blake, G. Seroussi and N. Smart, Cambridge University Press, 2005.
7. Galbraith SD, Paterson KG, Smart NP. Pairings for cryptographers, Discrete Applied Mathematics. 2008; 156(16):31133121.
8. Hankerson D, Menzes A, Vanstone S. Guide to Elliptic Curve Cryptography, Springer, New York, 2004.
9. Hardy GH, Wright EM. An introduction to the theory of numbers, oxford university press, United Kingdom, 1938.
10. Joux A. A one round protocol for tripartite Diffie-Hellman, Algorithmic Number Theory: 4th International Symposium, ANTS-IV, Lecture Notes in Computer Science, 2000; 1838: 385-393. Full version: Journal of Cryptology. 2004; 17:263-276.
11. Koblitz N. Elliptic Curve Cryptosystem, Journal of Mathematics Computation, 1987; 48(177):203-209.
12. Kumar M, Gupta P, Kumar A. A Novel and Secure Multi-party Key Exchange Scheme Using Trilinear Pairing Map Based on Elliptic Curve Cryptography, International Journal of Pure and Applied Mathematics, 2017; 116( 1).
13. Massoud HD, Reza A.Zero-Knowledge Identification Scheme Based on Weil Pairing. ISSN 1995-0802, Lobachevskii Journal of Mathematics. 2007; 30(3):203-207.
14. Miller VS. Use of elliptic curves in cryptography, Advances in Cryptology-CRYPTO, 85 (LNCS 218), 1985, 417-426.
15. Miller VS. The weil pairing and its efficient calculation, J. Cryptography. 2004; 17:235-261.
16. Miyaji A, Nakabayashi M, Takano S. New explicit conditions of elliptic curve traces for FR-reduction, EICE-Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2001; E84:1234-1243.
17. Morain F. Building cyclic elliptic curves modulo large primes, Advances in Cryptology, EUROCRYPT ' 91, Lecture Notes in Computer Science, 1991; 547:328-336.
18. Paterson KG. ID based signature from pairings on elliptic curves, Electron Lett., 2002; 38(18):1025-1026.
19. Sakai R, Ohgishi K, Kasahara M. Cryptosystems based on pairing over elliptic curve, In Proceedings of the 2000 Symposium on Cryptography and Information Security, Okinawa, Japan, 2000.
20. Shacham H. New Paradigms in Signature Schemes, PhD thesis, Stanford University, 2005.
21. Shamir A. Identity-based cryptosystems and signature schemes, In Advances in Cryptology-CRYPTO 84, Lect. Notes in Comput. Sci. 196, Springer-Verlag, 1985, 47-53.
22. Silverman J. The Arithmetic of Elliptic Curves, Springer-Verlag, New York, 1986.
23. Stinson DR. Cryptography theory and practice, Chapman and Hall/CRC, United Kingdom, 2006.
24. Washington LC. Elliptic curves number theory and cryptography, Chapman and Hall/CRC, United Kingdom, 2008.
25. Weil A. André Sur les fonctions algébriques à corps de constantes fini. (French) C. R. Acad. Sci. Paris, 1940; 210:592-594.
26. Zhang F, Kim K. ID based blind signature and ring signature from pairings, In Advances in Cryptology-ASIACRYPT, springer-verlag, 2002, 533-547.