Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

Pairings have found a range of applications in many areas of cryptography. As such, to utilize the enormous potential of pairing-based protocols one needs to efficiently compute pairings across various computing platforms. In this thesis, we give an introduction to pairing-based cryptography and describe the Tate pairing and its variants. We then describe some recent work to realize efficient computation of pairings. We further extend these optimizations and implement the O-Ate pairing on BN-curves on ARM and x86-64 platforms. Specifically, we extend the idea of lazy reduction to field inversion, optimize curve arithmetic, and construct efficient tower extensions to optimize field arithmetic. We also analyze the use of affine coordinates for pairing computation leading us to the conclusion that they are a competitive choice for fast pairing computation on ARM processors, especially at high security level. Our resulting implementation is more than three times faster than any previously reported implementation on ARM processors.

Elliptic Curve Cryptography (ECC), independently proposed by Miller [Mil86] and Koblitz [Kob87] in mid 80’s, is finding momentum to consolidate its status as the public-key system of choice in a wide range of applications and to further expand this position to settings traditionally occupied by RSA and DL-based systems. The non-existence of known subexponential attacks on this cryptosystem directly translates to shorter keylengths for a given security level and, consequently, has led to implementations with better bandwidth usage, reduced power and memory requirements, and higher speeds. Moreover, the dramatic entry of pairing-based cryptosystems defined on elliptic curves at the beginning of the new millennium has opened the possibility of a plethora of innovative applications, solving in some cases longstanding problems in cryptography. Nevertheless, public-key cryptography (PKC) is still relatively expensive in comparison with its symmetric-key counterpart and it remains an open challenge to reduce further the computing cost of the most time-consuming PKC primitives to guarantee their adoption for secure communication in commercial and Internet-based applications. The latter is especially true for pairing computations. Thus, it is of paramount importance to research methods which permit the efficient realization of Elliptic Curve and Pairing-based Cryptography on the several new platforms and applications. This thesis deals with efficient methods and explicit formulas for computing elliptic curve scalar multiplication and pairings over fields of large prime characteristic with the objective of enabling the realization of software implementations at very high speeds. To achieve this main goal in the case of elliptic curves, we accomplish the following tasks: identify the elliptic curve settings with the fastest arithmetic; accelerate the precomputation stage in the scalar multiplication; study number representations and scalar multiplication algorithms for speeding up the evaluation stage; identify most efficient field arithmetic algorithms and optimize them; analyze the architecture of the targeted platforms for maximizing the performance of ECC operations; identify most efficient coordinate systems and optimize explicit formulas; and realize implementations on x86-64 processors with an optimal algorithmic selection among all studied cases. In the case of pairings, the following tasks are accomplished: accelerate tower and curve arithmetic; identify most efficient tower and field arithmetic algorithms and optimize them; identify the curve setting with the fastest arithmetic and optimize it; identify state-of-the-art techniques for the Miller loop and final exponentiation; and realize an implementation on x86-64 processors with optimal algorithmic selection. The most outstanding contributions that have been achieved with the methodologies above in this thesis can be summarized as follows: • Two novel precomputation schemes are introduced and shown to achieve the lowest costs in the literature for different curve forms and scalar multiplication primitives. The detailed cost formulas of the schemes are derived for most relevant scenarios. • A new methodology based on the operation cost per bit to devise highly optimized and compact multibase algorithms is proposed. Derived multibase chains using bases {2,3} and {2,3,5} are shown to achieve the lowest theoretical costs for scalar multiplication on certain curve forms and for scenarios with and without precomputations. In addition, the zero and nonzero density formulas of the original (width-w) multibase NAF method are derived by using Markov chains. The application of “fractional” windows to the multibase method is described together with the derivation of the corresponding density formulas. • Incomplete reduction and branchless arithmetic techniques are optimally combined for devising high-performance field arithmetic. Efficient algorithms for “small” modular operations using suitably chosen pseudo-Mersenne primes are carefully analyzed and optimized for incomplete reduction. • Data dependencies between contiguous field operations are discovered to be a source of performance degradation on x86-64 processors. Three techniques for reducing the number of potential pipeline stalls due to these dependencies are proposed: field arithmetic scheduling, merging of point operations and merging of field operations. • Explicit formulas for two relevant cases, namely Weierstrass and Twisted Edwards curves over and , are carefully optimized employing incomplete reduction, minimal number of operations and reduced number of data dependencies between contiguous field operations. • Best algorithms for the field, point and scalar arithmetic, studied or proposed in this thesis, are brought together to realize four high-speed implementations on x86-64 processors at the 128-bit security level. Presented results set new speed records for elliptic curve scalar multiplication and introduce up to 34% of cost reduction in comparison with the best previous results in the literature. • A generalized lazy reduction technique that enables the elimination of up to 32% of modular reductions in the pairing computation is proposed. Further, a methodology that keeps intermediate results under Montgomery reduction boundaries maximizing operations without carry checks is introduced. Optimized formulas for the popular tower are explicitly stated and a detailed operation count that permits to determine the theoretical cost improvement attainable with the proposed method is carried out for the case of an optimal ate pairing on a Barreto-Naehrig (BN) curve at the 128-bit security level. • Best algorithms for the different stages of the pairing computation, including the proposed techniques and optimizations, are brought together to realize a high-speed implementation at the 128-bit security level. Presented results on x86-64 processors set new speed records for pairings, introducing up to 34% of cost reduction in comparison with the best published result. From a general viewpoint, the proposed methods and optimized formulas have a practical impact in the performance of cryptographic protocols based on elliptic curves and pairings in a wide range of applications. In particular, the introduced implementations represent a direct and significant improvement that may be exploited in performance-dominated applications such as high-demand Web servers in which millions of secure transactions need to be generated.

Bilinear pairings are being used in ingenious ways to solve various protocol problems. Much research has been done on improving the efficiency of pairing computations. This thesis gives an introduction to the Tate pairing and some variants including the ate pairing, Vercauteren's pairing, and the R-ate pairing. We describe the Barreto-Naehrig (BN) family of pairing-friendly curves, and analyze three different coordinates systems (affine, projective, and jacobian) for implementing the R-ate pairing. Finally, we examine some recent work for speeding the pairing computation and provide improved estimates of the pairing costs on a particular BN curve.

In this thesis, we explore the pairing-based cryptography on elliptic curves from the theoretical and implementation point of view. In this respect, we first study so-called pairing-friendly elliptic curves used in pairing-based cryptography. We classify these curves according to their construction methods and study them in details. Inspired of the work of Koblitz and Menezes, we study the elliptic curves in the form $y^{2}=x^{3}-c$ over the prime field $F_{q}$ and compute explicitly the number of points $#E(mathbb{F}_{q})$. In particular, we show that the elliptic curve $y^{2}=x^{3}-1$ over $mathbb{F}_{q}$ for the primes $q$ of the form $27A^{2}+1$ has an embedding degree $k=1$ and belongs to Scott-Barreto families in our classification. Finally, we give examples of those primes $q$ for which the security level of the pairing-based cryptographic protocols on the curve $y^{2}=x^{3}-1$ over $mathbb{F}_{q}$ is equivalent to 128-, 192-, or 256-bit AES keys. From the implementation point of view, it is well-known that one of the most important part of the pairing computation is final exponentiation. In this respect, we show explicitly how the final exponentiation is related to the linear recurrence relations. In particular, this correspondence gives that finding an algoritm to compute final exponentiation is equivalent to finding an algorithm to compute the $m$-th term of the associated linear recurrence relation. Furthermore, we list all those work studied in the literature so far and point out how the associated linear recurrence computed efficiently.

Elliptic Curve Cryptography (ECC), independently proposed by Miller [Mil86] and Koblitz [Kob87] in mid 80’s, is finding momentum to consolidate its status as the public-key system of choice in a wide range of applications and to further expand this position to settings traditionally occupied by RSA and DL-based systems. The non-existence of known subexponential attacks on this cryptosystem directly translates to shorter keylengths for a given security level and, consequently, has led to implementations with better bandwidth usage, reduced power and memory requirements, and higher speeds. Moreover, the dramatic entry of pairing-based cryptosystems defined on elliptic curves at the beginning of the new millennium has opened the possibility of a plethora of innovative applications, solving in some cases longstanding problems in cryptography. Nevertheless, public-key cryptography (PKC) is still relatively expensive in comparison with its symmetric-key counterpart and it remains an open challenge to reduce further the computing cost of the most time-consuming PKC primitives to guarantee their adoption for secure communication in commercial and Internet-based applications. The latter is especially true for pairing computations. Thus, it is of paramount importance to research methods which permit the efficient realization of Elliptic Curve and Pairing-based Cryptography on the several new platforms and applications. This thesis deals with efficient methods and explicit formulas for computing elliptic curve scalar multiplication and pairings over fields of large prime characteristic with the objective of enabling the realization of software implementations at very high speeds. To achieve this main goal in the case of elliptic curves, we accomplish the following tasks: identify the elliptic curve settings with the fastest arithmetic; accelerate the precomputation stage in the scalar multiplication; study number representations and scalar multiplication algorithms for speeding up the evaluation stage; identify most efficient field arithmetic algorithms and optimize them; analyze the architecture of the targeted platforms for maximizing the performance of ECC operations; identify most efficient coordinate systems and optimize explicit formulas; and realize implementations on x86-64 processors with an optimal algorithmic selection among all studied cases. In the case of pairings, the following tasks are accomplished: accelerate tower and curve arithmetic; identify most efficient tower and field arithmetic algorithms and optimize them; identify the curve setting with the fastest arithmetic and optimize it; identify state-of-the-art techniques for the Miller loop and final exponentiation; and realize an implementation on x86-64 processors with optimal algorithmic selection. The most outstanding contributions that have been achieved with the methodologies above in this thesis can be summarized as follows: • Two novel precomputation schemes are introduced and shown to achieve the lowest costs in the literature for different curve forms and scalar multiplication primitives. The detailed cost formulas of the schemes are derived for most relevant scenarios. • A new methodology based on the operation cost per bit to devise highly optimized and compact multibase algorithms is proposed. Derived multibase chains using bases {2,3} and {2,3,5} are shown to achieve the lowest theoretical costs for scalar multiplication on certain curve forms and for scenarios with and without precomputations. In addition, the zero and nonzero density formulas of the original (width-w) multibase NAF method are derived by using Markov chains. The application of “fractional” windows to the multibase method is described together with the derivation of the corresponding density formulas. • Incomplete reduction and branchless arithmetic techniques are optimally combined for devising high-performance field arithmetic. Efficient algorithms for “small” modular operations using suitably chosen pseudo-Mersenne primes are carefully analyzed and optimized for incomplete reduction. • Data dependencies between contiguous field operations are discovered to be a source of performance degradation on x86-64 processors. Three techniques for reducing the number of potential pipeline stalls due to these dependencies are proposed: field arithmetic scheduling, merging of point operations and merging of field operations. • Explicit formulas for two relevant cases, namely Weierstrass and Twisted Edwards curves over and , are carefully optimized employing incomplete reduction, minimal number of operations and reduced number of data dependencies between contiguous field operations. • Best algorithms for the field, point and scalar arithmetic, studied or proposed in this thesis, are brought together to realize four high-speed implementations on x86-64 processors at the 128-bit security level. Presented results set new speed records for elliptic curve scalar multiplication and introduce up to 34% of cost reduction in comparison with the best previous results in the literature. • A generalized lazy reduction technique that enables the elimination of up to 32% of modular reductions in the pairing computation is proposed. Further, a methodology that keeps intermediate results under Montgomery reduction boundaries maximizing operations without carry checks is introduced. Optimized formulas for the popular tower are explicitly stated and a detailed operation count that permits to determine the theoretical cost improvement attainable with the proposed method is carried out for the case of an optimal ate pairing on a Barreto-Naehrig (BN) curve at the 128-bit security level. • Best algorithms for the different stages of the pairing computation, including the proposed techniques and optimizations, are brought together to realize a high-speed implementation at the 128-bit security level. Presented results on x86-64 processors set new speed records for pairings, introducing up to 34% of cost reduction in comparison with the best published result. From a general viewpoint, the proposed methods and optimized formulas have a practical impact in the performance of cryptographic protocols based on elliptic curves and pairings in a wide range of applications. In particular, the introduced implementations represent a direct and significant improvement that may be exploited in performance-dominated applications such as high-demand Web servers in which millions of secure transactions need to be generated.

Bilinear pairings are being used in ingenious ways to solve various protocol problems. Much research has been done on improving the efficiency of pairing computations. This thesis gives an introduction to the Tate pairing and some variants including the ate pairing, Vercauteren's pairing, and the R-ate pairing. We describe the Barreto-Naehrig (BN) family of pairing-friendly curves, and analyze three different coordinates systems (affine, projective, and jacobian) for implementing the R-ate pairing. Finally, we examine some recent work for speeding the pairing computation and provide improved estimates of the pairing costs on a particular BN curve.

Pairings have found a range of applications in many areas of cryptography. As such, to utilize the enormous potential of pairing-based protocols one needs to efficiently compute pairings across various computing platforms. In this thesis, we give an introduction to pairing-based cryptography and describe the Tate pairing and its variants. We then describe some recent work to realize efficient computation of pairings. We further extend these optimizations and implement the O-Ate pairing on BN-curves on ARM and x86-64 platforms. Specifically, we extend the idea of lazy reduction to field inversion, optimize curve arithmetic, and construct efficient tower extensions to optimize field arithmetic. We also analyze the use of affine coordinates for pairing computation leading us to the conclusion that they are a competitive choice for fast pairing computation on ARM processors, especially at high security level. Our resulting implementation is more than three times faster than any previously reported implementation on ARM processors.

Identity based cryptography was first proposed by Shamir in 1984. Rather than deriving a public key from private information, which would be the case in traditional public key encryption schemes, in identity based schemes a user's identity plays the role of the public key. This reduces the amount of computations required for authentication, and simplifies key-management. Efficient and strong implementations of identity based schemes are based around easily computable bilinear mappings of two points on an elliptic curve onto a multiplicative subgroup of a field, also called pairing. The idea of utilizing the identity of the user simplifies the public key infrastructure. However, since pairing computations are expensive for both area and timing, the proposed identity based cryptosystem are hard to implement. In order to be able to efficiently utilize the idea of identity based cryptography, there is a strong need for an efficient pairing implementations. Pairing computations could be realized in multiple fields. Since the main building block and the bottleneck of the algorithm is multiplication, we focused our research on building a fast and small arithmetic core that can work on multiple fields. This would allow a single piece of hardware to realize a wide spectrum of cryptographic algorithms, including pairings, with minimal amount of software coding. We present a novel unified core design which is extended to realize Montgomery multiplication in the fields GF(2^n), GF(3^m), and GF(p). Our unified design supports RSA and elliptic curve schemes, as well as identity based encryption which requires a pairing computation on an elliptic curve. The architecture is pipelined and is highly scalable. The unified core utilizes the redundant signed digit representation to reduce the critical path delay. While the carry-save representation used in classical unified architectures is only good for addition and multiplication operations, the redundant signed digit representation also facilitates efficient computation of comparison and subtraction operations besides addition and multiplication. Thus, there is no need for transformation between the redundant and non-redundant representations of field elements, which would be required in classical unified architectures to realize the subtraction and comparison operations. We also quantify the benefits of unified architectures in terms of area and critical path delay. We provide detailed implementation results. The metric shows that the new unified architecture provides an improvement over a hypothetical non-unified architecture of at least 24.88 % while the improvement over a classical unified architecture is at least 32.07 %. Until recently there has been no work covering the security of pairing based cryptographic hardware in the presence of side-channel attacks, despite their apparent suitability for identity-aware personal security devices, such as smart cards. We present a novel non-linear error coding framework which incorporates strong adversarial fault detection capabilities into identity based encryption schemes built using Tate pairing computations. The presented algorithms provide quantifiable resilience in a well defined strong attacker model. Given the emergence of fault attacks as a serious threat to pairing based cryptography, the proposed technique solves a key problem when incorporated into software and hardware implementations. In this dissertation, we also present an efficient accelerator for computing the Tate Pairing in characteristic 3, based on the Modified Duursma Lee algorithm.