72 results sorted by ID
Possible spell-corrected query: are pairing
Efficient Implementation of Super-optimal Pairings on Curves with Small Prime Fields at the 192-bit Security Level
Jianming Lin, Chang-An Zhao, Yuhao Zheng
Implementation
For many pairing-based cryptographic protocols such as Direct Anonymous Attestation (DAA) schemes, the arithmetic on the first pairing subgroup $\mathbb{G}_1$ is more fundamental. Such operations heavily depend on the sizes of prime fields. At the 192-bit security level, Gasnier and Guillevic presented a curve named GG22D7-457 with CM-discriminant $D = 7$ and embedding degree $k = 22$. Compared to other well-known pairing-friendly curves at the same security level, the curve GG22D7-457 has...
Accelerating pairings on BW10 and BW14 Curves
Senegue Gomez Nyamsi, Laurian Guimagang Azebaze, Emmanuel Fouotsa
Implementation
Since the advent of pairing based cryptography, many researchers have developed several techniques and variants of pairings to optimise the speed of pairing computations. The selection of the elliptic curve for a given pairing based protocol is crucial for operations in the first and second pairing groups of points of the elliptic curve and for many cryptographic schemes. A new variant of superoptimal pairing was proposed in 2023, namely x-superoptimal pairing on curves with odd prime...
Fast pairings via biextensions and cubical arithmetic
Damien Robert
Foundations
Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, \ldots, pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions.
This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt...
Faster Beta Weil Pairing on BLS Pairing Friendly Curves with Odd Embedding Degree
Azebaze Guimagang Laurian, Fouotsa Emmanuel, El Mrabet Nadia, Pecha Njiahouo Aminatou
Foundations
Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the...
x-Superoptimal Pairings on some Elliptic Curves with Odd Prime Embedding Degrees
Emmanuel Fouotsa, Azebaze Guimagang Laurian, Ayissi Raoul
Foundations
The choice of the elliptic curve for a given pairing based protocol
is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous
attestation, etc) or accumulators, operations in the first pairing group $\mathbb{G}$ of points of the elliptic curve is more predominant. At $128$-bit security level two curves $BW13-P310$ and $BW19-P286$ with odd embedding degrees $13$ and $19$ suitable for super optimal pairing have been recommended for...
Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings
Patrick Longa
Public-key cryptography
We propose a novel approach that generalizes interleaved modular multiplication algorithms for the computation of sums of products over large prime fields. This operation has widespread use and is at the core of many cryptographic applications. The method reformulates the widely used lazy reduction technique, crucially avoiding the need for storage and computation of "double-precision" operations. Moreover, it can be easily adapted to the different methods that exist to compute modular...
Families of SNARK-friendly 2-chains of elliptic curves
Youssef El Housni, Aurore Guillevic
Public-key cryptography
At CANS’20, El Housni and Guillevic introduced a new 2-chain of pairing-friendly elliptic curves for recursive zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) made of the former BLS12-377 curve (a Barreto–Lynn–Scott curve over a 377- bit prime field) and the new BW6-761 curve (a Brezing–Weng curve of embedding degree 6 over a 761-bit prime field). First we generalise the curve construction, the pairing formulas (e : G1 × G2 → GT ) and the group operations to any...
Software Implementation of Optimal Pairings on Elliptic Curves with Odd Prime Embedding Degrees
Yu Dai, Zijian Zhou, Fangguo Zhang, Chang-An Zhao
Public-key cryptography
Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves,
instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy...
2021/1142
Last updated: 2021-09-13
The Elliptic Net Algorithm Revisited
Shiping Cai, Zhi Hu, Zheng-An Yao, Chang-An Zhao
Implementation
Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...
Efficient Final Exponentiation via Cyclotomic Structure for Pairings over Families of Elliptic Curves
Daiki Hayashida, Kenichiro Hayasaka, Tadanori Teruya
Public-key cryptography
The final exponentiation, which is the exponentiation by a fixed large exponent, must be performed in the Tate and (optimal) Ate pairing computation to ensure output uniqueness, algorithmic correctness, and security for pairing-based cryptography. In this paper, we propose a new framework of efficient final exponentiation for pairings over families of elliptic curves. Our framework provides two methods: the first method supports families of elliptic curves with arbitrary embedding degrees,...
Optimal TNFS-secure pairings on elliptic curves with composite embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation
Aurore Guillevic, Simon Masson, Emmanuel Thomé
Public-key cryptography
Recent algorithmic improvements of discrete logarithm computation in special extension fields threaten the security of pairing-friendly curves used in practice. A possible answer to this delicate situation is to propose alternative curves that are immune to these attacks, without compromising the efficiency of the pairing computation too much. We follow this direction, and focus on embedding degrees 5 to 8; we extend the Cocks-Pinch algorithm to obtain pairing-friendly curves with an...
Anonymous Attestation for IoT
Santosh Ghosh, Andrew H. Reinders, Rafael Misoczki, Manoj R. Sastry
Implementation
Internet of Things (IoT) have seen tremendous growth and are being deployed pervasively in areas such as home, surveillance, health-care and transportation. These devices collect and process sensitive data with respect to user's privacy. Protecting the privacy of the user is an essential aspect of security, and anonymous attestation of IoT devices are critical to enable privacy-preserving mechanisms. Enhanced Privacy ID (EPID) is an industry-standard cryptographic scheme that offers...
Pairing-Friendly Twisted Hessian Curves
Chitchanok Chuengsatiansup, Chloe Martindale
Public-key cryptography
This paper presents efficient formulas to compute Miller doubling and Miller addition utilizing degree-3 twists on curves with j-invariant 0 written in Hessian form. We give the formulas for both odd and even embedding degrees and for pairings on both $\mathbb{G}_1\times\mathbb{G}_2$ and $\mathbb{G}_2\times\mathbb{G}_1$. We propose the use of embedding degrees 15 and 21 for 128-bit and 192-bit security respectively in light of the NFS attacks and their variants. We give a comprehensive...
Turning HATE Into LOVE: Compact Homomorphic Ad Hoc Threshold Encryption for Scalable MPC
Leonid Reyzin, Adam Smith, Sophia Yakoubov
In a public-key threshold encryption scheme, the sender produces a single ciphertext, and any $t+1$ out of $n$ intended recipients can combine their partial decryptions to obtain the plaintext. Ad hoc threshold encryption (ATE) schemes require no correlated setup, enabling each party to simply generate its own key pair. In this paper, we initiate a systematic study of the possibilities and limitations of ad-hoc threshold encryption, and introduce a key application to scalable multiparty...
Optimal TNFS-secure pairings on elliptic curves with even embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
Efficient Optimal Ate Pairing at 128-bit Security Level
Md. Al-Amin Khandaker, Yuki Nanjo, Loubna Ghammam, Sylvain Duquesne, Yasuyuki Nogami, Yuta Kodera
Public-key cryptography
Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and...
Computing Optimal Ate Pairings on Elliptic Curves with Embedding Degree $9,15$ and $27$
Emmanuel Fouotsa, Nadia El Mrabet, Aminatou Pecha
Much attention has been given to efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The existing few works in the case of odd embedding degrees require some improvements.
This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9, 15 \mbox{ and } 27$ which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower...
Adequate Elliptic Curve for Computing the Product of n Pairings
Loubna Ghammam, Emmanuel Fouotsa
Foundations
Many pairing-based protocols require the computation of the product
and/or of a quotient of n pairings where n > 1 is a natural integer.
Zhang et al.[1] recently showed that the Kachisa-Schafer and Scott family
of elliptic curves with embedding degree 16 denoted KSS16 at the 192-bit
security level is suitable for such protocols comparatively to the Baretto-
Lynn and Scott family of elliptic curves of embedding degree 12 (BLS12).
In this work, we provide important corrections and improvements...
On the Computation of the Optimal Ate Pairing at the 192-bit Security Level
Loubna Ghammam, Emmanuel Fouotsa
Barreto, Lynn and Scott elliptic curves of embedding degree
12 denoted BLS12 have been proven to present fastest results on the
implementation of pairings at the 192-bit security level [1]. The computation
of pairings in general involves the execution of the Miller algorithm
and the final exponentiation. In this paper, we improve the complexity
of these two steps up to 8% by searching an appropriate parameter. We
compute the optimal ate pairing on BLS curves of embedding degree 12
and we...
Area-Efficient Hardware Implementation of the Optimal Ate Pairing over BN curves.
Anissa Sghaier, Loubna Ghammam, Medyen Zeghid, Sylvain Duquesne, Mohsen Machhout
To have an efficient asymmetric key encryption scheme such as elliptic curves,
hyperelliptic curves, pairing etc., we have to go through an arithmetic optimization
then a hardware one. Taking into consideration restricted environments’ compromises,
we should strike a balance between efficiency and memory resources. For
this reason, we studied the mathematical aspect of pairing computation and gave
new development of the methods that compute the hard part of the final exponentiation
in [2]....
Inverting the Final exponentiation of Tate pairings on ordinary elliptic curves using faults
Ronan Lashermes, Jacques Fournier, Louis Goubin
Public-key cryptography
The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special `easy' cases or even showed that...
Efficient Pairings Computation on Jacobi Quartic Elliptic Curves
Sylvain Duquesne, Nadia El Mrabet, Emmanuel Fouotsa
Public-key cryptography
This paper proposes the computation of the Tate pairing,
Ate pairing and its variations on the special Jacobi quartic elliptic curve
Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller's
algorithm to compute the Tate pairing. We use the birational equivalence
between Jacobi quartic curves and Weierstrass curves, together with a
specific point representation to obtain the best result to date among
curves with quartic twists. For the doubling and addition steps in...
Self-pairings on supersingular elliptic curves with embedding degree $three$
Binglong Chen, Chang-An Zhao
Public-key cryptography
Self-pairings are a special subclass of pairings and
have interesting applications in cryptographic schemes and protocols. In this paper, we explore the computation of the self-pairings on supersingular elliptic curves with embedding degree $k = 3$. We construct a novel self-pairing which has the same Miller loop as the Eta/Ate pairing. However, the proposed self-pairing has a simple final exponentiation. Our results suggest that the proposed self-pairings are more efficient than the other...
On a Relation between the Ate Pairing and the Weil Pairing for Supersingular Elliptic Curves
Takakazu Satoh
Public-key cryptography
The hyperelliptic curve Ate pairing provides an efficient way to compute a
bilinear pairing on the Jacobian variety of a hyperelliptic curve.
We prove that, for supersingular elliptic curves with embedding degree
two, square of the Ate pairing is nothing but the Weil pairing.
Using the formula, we develop an X-coordinate only pairing inversion method.
However, the algorithm is still infeasible for cryptographic size problems.
Golden Sequence for the PPSS Broadcast Encryption Scheme with an Asymmetric Pairing
Renaud Dubois, Margaux Dugardin, Aurore Guillevic
Implementation
Broadcast encryption is conventionally formalized as broadcast encapsulation in which, instead of a cipher-
text, a session key is produced, which is required to be indistinguishable from random. Such a scheme can
provide public encryption functionality in combination with a symmetric encryption through the hybrid en-
cryption paradigm. The Boneh-Gentry-Waters scheme of 2005 proposed a broadcast scheme with constant-size
ciphertext. It is one of the most efficient broadcast encryption...
A Fast Implementation of the Optimal Ate Pairing over BN curve on Intel Haswell Processor
Shigeo MITSUNARI
Implementation
We present an efficient implementation of the Optimal Ate Pairing on Barreto-Naehrig
curve over a 254-bit prime field on Intel Haswell processor.
Our library is able to compute the optimal ate pairing over a 254-bit prime field,
in just 1.17 million of clock cycles on a single core of an Intel Core i7-4700MQ(2.4GHz)
processor with TurboBoost technology disabled.
Pairing Inversion via Non-degenerate Auxiliary Pairings
Seunghwan Chang, Hoon Hong, Eunjeong Lee, Hyang-Sook Lee
The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem(PI). In this paper, we discuss the difficulty of pairing inversion on the generalized ate pairings of Vercauteren.
First, we provide a simpler approach for PI by generalizing and simplifying Kanayama-Okamoto’s approach; our approach involves modifications of exponentiation inversion(EI) and Miller inversion(MI), via an “auxiliary” pairing. Then we provide a...
Comparing the Pairing Efficiency over Composite-Order and Prime-Order Elliptic Curves
Aurore Guillevic
Implementation
We provide software implementation timings for pairings over
composite-order and prime-order elliptic curves. Composite orders must be large enough to be infeasible to factor. They are modulus of 2 up to 5 large prime numbers in the literature. There exists size recommendations for two-prime RSA modulus and we extend the results of Lenstra concerning the RSA modulus sizes to multi-prime modulus, for various security levels. We then implement a Tate pairing over a composite order...
A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties
David Lubicz, Damien Robert
Foundations
In this paper, we use the theory of theta functions to generalize to
all abelian varieties the usual Miller's algorithm to compute a
function associated to a principal divisor. We also explain how to
use the Frobenius morphism on abelian varieties defined over a
finite field in order to shorten the loop of the Weil and Tate
pairings algorithms. This extend preceding results about ate and
twisted ate pairings to all abelian varieties. Then building upon
the two preceding ingredients, we...
Speeding up Ate Pairing Computation in Affine Coordinates
Duc-Phong Le, Chik How Tan
At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates.
On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in...
Fixed Argument Pairing Inversion on Elliptic Curves
Sungwook Kim, Jung Hee Cheon
Public-key cryptography
Let $E$ be an elliptic curve over a finite field ${\mathbb F}_q$ with a power of prime $q$, $r$ a prime dividing $\#E({\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r | \Phi_k(p)$, called embedding degree. Then a bilinear map $t: E({\mathbb F}_q)[r] \times E({\mathbb F}_{q^k})/rE({\mathbb F}_{q^k}) \rightarrow {\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. And the Ate pairing and other variants are obtained by reducing the domain for each argument and raising...
Efficient Implementation of Bilinear Pairings on ARM Processors
Gurleen Grewal, Reza Azarderakhsh, Patrick Longa, Shi Hu, David Jao
As hardware capabilities increase, low-power devices such
as smartphones represent a natural environment for the efficient
implementation of cryptographic pairings. Few works in the literature
have considered such platforms despite their growing importance in a
post-PC world. In this paper, we investigate the efficient computation
of the Optimal-Ate pairing over Barreto-Naehrig curves in software at
different security levels on ARM processors. We exploit
state-of-the-art techniques and...
On Efficient Pairings on Elliptic Curves over Extension Fields
Xusheng Zhang, Kunpeng Wang, Dongdai Lin
Implementation
In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics.
In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller's...
Fault Attack against Miller's algorithm
Nadia El Mrabet
Public-key cryptography
We complete the study of [23] and [27] about Miller's algorithm. Miller's algorithm is
a central step to compute the Weil, Tate and Ate pairings. The aim of this article is to analyze the
weakness of Miller's algorithm when it undergoes a fault attack. We prove that Miller's algorithm
is vulnerable to a fault attack which is valid in all coordinate systems, through the resolution of a
nonlinear system. We highlight the fact that putting the secret as the rst argument of the pairing
is not a...
Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings
Craig Costello, Kristin Lauter, Michael Naehrig
Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfamilies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations.
Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific...
A High Speed Pairing Coprocessor Using RNS and Lazy Reduction
Gavin Xiaoxu Yao, Junfeng Fan, Ray C. C. Cheung, Ingrid Verbauwhede
Implementation
In this paper, we present a high speed pairing coprocessor using Residue Number System (RNS) and lazy reduction. We show that combining RNS, which are naturally suitable for parallel architectures, and lazy reduction, which performs one reduction for more than one multiplication, the computational complexity of pairings can be largely reduced. The design is prototyped on a Xilinx Virtex-6 FPGA, which utilizes 7023 slices and 32 DSPs, and finishes one 254-bit optimal ate pairing computation...
Affine Pairings on ARM
Tolga Acar, Kristin Lauter, Michael Naehrig, Daniel Shumow
Implementation
Pairings on elliptic curves are being used in an increasing number of cryptographic applications on many different devices and platforms, but few performance numbers for cryptographic pairings have been reported on embedded and mobile devices.
In this paper we give performance numbers for affine and projective pairings on a dual-core Cortex A9 ARM processor and compare performance of the same implementation across three platforms: x86, x86-64 and ARM. Using a fast inversion in the base...
A Family of Implementation-Friendly BN Elliptic Curves
Geovandro C. C. F. Pereira, Marcos A. Simplício Jr, Michael Naehrig, Paulo S. L. M. Barreto
For the last decade, elliptic curve cryptography has gained increasing interest in industry and in the academic community. This is especially due to the high level of security it provides with relatively small keys and to its ability to create very efficient and multifunctional cryptographic schemes by means of bilinear pairings. Pairings require pairing-friendly elliptic curves and among the possible choices, Barreto-Naehrig (BN) curves arguably constitute one of the most versatile...
An Analysis of Affine Coordinates for Pairing Computation
Kristin Lauter, Peter L. Montgomery, Michael Naehrig
Implementation
In this paper we analyze the use of affine coordinates for pairing computation. We observe that in many practical settings, for example when implementing optimal ate pairings in high security levels, affine coordinates are faster than using the best currently known formulas for projective coordinates. This observation relies on two known techniques for speeding up field inversions which we analyze in the context of pairing computation. We give detailed performance numbers for a pairing...
High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves
Jean-Luc Beuchat, Jorge Enrique González Díaz, Shigeo Mitsunari, Eiji Okamoto, Francisco Rodríguez-Henríquez, Tadanori Teruya
Implementation
This paper describes the design of a fast software library for the computation of the optimal ate pairing on a Barreto--Naehrig elliptic curve. Our library is able to compute the optimal ate pairing over a $254$-bit prime field $\mathbb{F}_{p}$, in just $2.63$ million of clock cycles on a single core of an Intel Core i7 $2.8$GHz processor, which implies that the pairing computation takes $0.942$msec. We are able to achieve this performance by a careful implementation of the base field...
Cryptographic Pairings Based on Elliptic Nets
Naoki Ogura, Naoki Kanayama, Shigenori Uchiyama, Eiji Okamoto
In 2007, Stange proposed a novel method of computing the Tate pairing on an elliptic curve over a finite field.
This method is based on elliptic nets,
which are maps from $\mathbb{Z}^n$ to a ring that satisfy a certain recurrence relation.
In this paper, we explicitly give formulae for computing some variants
of the Tate pairing:
Ate, Ate$_i$, R-Ate and Optimal pairings, based on elliptic nets.
We also discuss their efficiency by using some experimental results.
Fixed Argument Pairings
Craig Costello, Douglas Stebila
A common scenario in many pairing-based cryptographic protocols is that one argument in the pairing is fixed as a long term secret key or a constant parameter in the system. In these situations, the runtime of Miller’s algorithm can be significantly reduced by storing precomputed values that depend on the fixed argument, prior to the input or existence of the second argument. In light of recent developments in pairing computation, we show that the computation of the Miller...
New software speed records for cryptographic pairings
Michael Naehrig, Ruben Niederhagen, Peter Schwabe
Implementation
This paper presents new software speed records for the computation
of cryptographic pairings. More specifically, we present details of an implementation which computes the optimal ate pairing
on a 256-bit Barreto-Naehrig curve in only 4,379,912 cycles
on one core of an Intel Core 2 Quad Q9550 processor.
This speed is achieved by combining
1.) state-of-the-art high-level optimization techniques,
2.) a new representation of elements
in the underlying finite fields which makes
use of the...
Delaying Mismatched Field Multiplications in Pairing Computations
Craig Costello, Colin Boyd, Juan Manuel Gonzalez Nieto, Kenneth Koon-Ho Wong
Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations....
Avoiding Full Extension Field Arithmetic in Pairing Computations
Craig Costello, Colin Boyd, Juan Manuel Gonzalez Nieto, Kenneth Koon-Ho Wong
The most costly operations encountered in pairing computations are those that take place in the full extension field $\mathbb{F}_{p^k}$. At high levels of security, the complexity of operations in $\mathbb{F}_{p^k}$ dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller's algorithm. Many recent optimizations in the literature have focussed on improving the overall...
Universally Constructing 12-th Degree Extension Field for Ate Pairing
Masaaki Shirase
Public-key cryptography
We need to perform arithmetic in $\Fpt$ to use Ate pairing on a Barreto-Naehrig (BN) curve, where $p(z)$ is a prime given by $p(z)=36z^4+36z^3+24z^2+6z+1$ with an integer $z$. In many implementations of Ate pairing, $\Fpt$ has been regarded as the 6-th extension of $\Fpp$, and it has been constructed as $\Fpt=\Fpp[v]/(v^6-\xi)$ for an element $\xi\in \Fpp$ such that $v^6-\xi$ is irreducible in $\Fpp[v]$. Such $\xi$ depends on the value of $p(z)$, and we may use mathematic software to find...
Faster Pairing Computations on Curves with High-Degree Twists
Craig Costello, Tanja Lange, Michael Naehrig
Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than $2$ is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that...
Optimal pairing revisited
Mingqiang Wang, Puwen Wei, Haifeng Zhang, Yuliang Zheng
Implementation
Vercauteren introduced
a notion of optimal pairings. Up to know the only known optimal
pairing is the optimal Ate pairing. In this paper, we give some
properties of optimal pairing and provide an algorithm for finding
an optimal pairing if there exists one which is defined on the given
elliptic curve. Applying the cyclotomic polynomial, we construct
some new optimal pairings and provide a construction method of
pairing-friendly elliptic curves on which the optimal pairing can be
defined....
A study of pairing computation for elliptic curves with embedding degree 15
Nadia El Mrabet, Nicolas Guillermin, Sorina Ionica
Implementation
This paper presents the first study of pairing computation on curves with embedding degree $15$. We compute the Ate and the twisted Ate pairing for a family of curves with parameter $\rho~1.5$ and embedding degree $15$. We use a twist of degree 3 to perform most of the operations in $\F_p$ or $\F_{p^5}$. Furthermore, we present a new arithmetic for extension fields of degree $5$. Our computations show that these curves give very efficient implementations for pairing-based cryptography at...
Implementing cryptographic pairings: a magma tutorial
Luis J Dominguez Perez, Ezekiel J Kachisa, Michael Scott
Implementation
In this paper we show an efficient implementation if the Tate, ate, and R-ate pairings in magma. This will be demostrated by using the KSS curves with embedding degree k=18
Designing an ASIP for Cryptographic Pairings over Barreto-Naehrig Curves
David Kammler, Diandian Zhang, Peter Schwabe, Hanno Scharwaechter, Markus Langenberg, Dominik Auras, Gerd Ascheid, Rainer Leupers, Rudolf Mathar, Heinrich Meyr
Implementation
This paper presents a design-space exploration of an application-specific instruction-set
processor (ASIP) for the computation of various cryptographic pairings over Barreto-Naehrig
curves (BN curves). Cryptographic pairings are based on elliptic curves over finite fields--in
the case of BN curves a field Fp of large prime order p. Efficient arithmetic in these fields is
crucial for fast computation of pairings. Moreover, computation of cryptographic pairings is
much more complex than...
On the final exponentiation for calculating pairings on ordinary elliptic curves
Michael Scott, Naomi Benger, Manuel Charlemagne, Luis J. Dominguez Perez, Ezekiel J. Kachisa
Implementation
When using pairing-friendly ordinary elliptic curves to compute the Tate and related pairings, the computation consists of two main components, the Miller loop and the so-called final exponentiation. As a result of good progress being made to reduce the Miller loop component of the algorithm (particularly with the discovery of
``truncated loop'' pairings like the R-ate pairing), the final exponentiation has become a more significant component of the overall calculation. Here we exploit the...
Twisted Ate Pairing on Hyperelliptic Curves and Applications
Fangguo Zhang
In this paper we show that the twisted Ate pairing on elliptic curves can be generalized to hyperelliptic curves, we also give a series of variations of the hyperelliptic Ate and twisted Ate pairings. Using the hyperelliptic Ate pairing and twisted Ate
pairing, we propose a new approach to speed up the Weil pairing computation, and obtain an interested result: For some hyperelliptic curves with high degree twist, using this approach to compute Weil pairing will be faster than Tate pairing,...
Reducing the Complexity of the Weil Pairing Computation
Chang-An Zhao, Fangguo Zhang, Dongqing Xie
In this paper, we present some new variants based on the Weil pairing for efficient pairing computations. The new pairing variants have the short Miller iteration loop and simple final exponentiation. We then show that computing the proposed pairings is more efficient than computing the Weil pairing. Experimental results for these pairings are also given.
Polynomials for Ate Pairing and $\mathbf{Ate}_{i}$ Pairing
Zhitu Su, Hui Li, JianFeng Ma
Public-key cryptography
The irreducible factor $r(x)$ of $\mathrm{\Phi}_{k}(u(x))$ and $u(x)
$ are often used in constructing pairing-friendly curves. $u(x)$ and
$u_{c} \equiv u(x)^{c} \pmod{r(x)}$ are selected to be the Miller
loop control polynomial in Ate pairing and $\mathrm{Ate}_{i}$
pairing. In this paper we show that when $4|k$ or the minimal prime
which divides $k$ is larger than $2$, some $u(x)$ and $r(x)$ can not
be used as curve generation parameters if we want $\mathrm{Ate}_{i}$
pairing to be efficient....
Optimal Pairings
F. Vercauteren
Public-key cryptography
In this paper we introduce the concept of an \emph{optimal pairing}, which by definition can be computed using only $\log_2 r/ \varphi(k)$ basic Miller iterations, with $r$ the order of the groups involved and $k$ the embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any non-degenerate pairing on an elliptic curve without efficiently computable endomorphisms different...
All Pairings Are in a Group
Chang-An Zhao, Fangguo Zhang, Jiwu Huang
In this paper, we suggest that all pairings be in a group from an
abstract angle. It is possible that our observation can be applied
into other aspects of pairing-based cryptosystems.
Efficient and Generalized Pairing Computation on Abelian Varieties
Eunjeong Lee, Hyang-Sook Lee, Cheol-Min Park
Public-key cryptography
In this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the R-ate pairing. This pairing is a generalization of the Ate and Ate_i pairing, and also improves efficiency of the pairing computation. Using the R-ate pairing, the loop length in Miller's algorithm can be as small as ${\rm log}(r^{1 / \phi(k)})$ for some pairing-friendly elliptic curves which have not reached this lower bound. Therefore we obtain from 29 % to 69 % savings...
Computing Pairings Using x-Coordinates Only
Steven D. Galbraith, Xibin Lin
To reduce bandwidth in elliptic curve cryptography one can transmit
only $x$-coordinates of points (or $x$-coordinates together with an
extra bit). For further computation using the points one can either
recover the $y$-coordinates by taking square roots or one can use
point multiplication formulae which use $x$-coordinates only.
We consider how to efficiently use point compression in
pairing-based cryptography. We give a method to compute compressed
Weil pairings using $x$-coordinates...
Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic field
Ezekiel J. Kachisa, Edward F. Schaefer, Michael Scott
Public-key cryptography
We describe a new method for constructing Brezing-Weng-like pairing-friendly elliptic curves. The new construction uses the minimal polynomials of elements in a cyclotomic field. Using this new construction we present new ``record breaking'' families of pairing-friendly curves with embedding degrees of $k \in \{16,18,36,40\}$, and
some interesting new constructions for the cases $k \in \{8,32\}$
Computing the Ate Pairing on Elliptic Curves with Embedding Degree $k=9$
Xibin Lin, Chang-An Zhao, Fangguo Zhang, Yanming Wang
For AES 128 security level there are several natural choices for
pairing-friendly elliptic curves. In particular, as we will explain,
one might choose curves with $k=9$ or curves with $k=12$. The case
$k=9$ has not been studied in the literature, and so it is not clear
how efficiently pairings can be computed in that case. In this
paper, we present efficient methods for the $k=9$ case, including
generation of elliptic curves with the shorter Miller loop, the
denominator elimination and...
On compressible pairings and their computation
Michael Naehrig, Paulo S. L. M. Barreto, Peter Schwabe
Public-key cryptography
In this paper we provide explicit formul\ae\ to compute bilinear pairings in compressed form. We indicate families of curves where the proposed compressed computation method can be applied and where particularly generalized versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. Our approach introduces more flexibility when trading off computation speed and memory requirement. Furthermore, compressed computation of reduced pairings can be done without any...
Implementing Cryptographic Pairings over Curves of Embedding Degrees 8 and 10
Christine Abegail Antonio, Satoru Tanaka, Ken Nakamula
Implementation
In this paper, we will describe efficient implementations of
the Tate and Ate pairings over ordinary elliptic curves of embedding degrees
8 and 10. We will discuss the possible curve-dependent optimizations
that can be applied to evaluate the pairings. We pay particular
attention to the use of elliptic curve twists and the denominator elimination
method to make computations more efficient. Our main goal is
to draw together the best possible optimizations that can be used to
efficiently...
Implementing Cryptographic Pairings over Barreto-Naehrig Curves
Augusto Jun Devegili, Michael Scott, Ricardo Dahab
Implementation
In this paper we describe an efficient implementation of the Tate and Ate pairings using Barreto-Naehrig pairing-friendly curves, on both a
standard 32-bit PC and on a 32-bit smartcard. First we introduce a sub-family of such curves with a particularly simple representation. Next we consider the issues that arise in the efficient implementation of field arithmetic in $\F_{p^{12}}$, which is crucial to good performance. Various optimisations are suggested, including a novel approach to the...
A Note on the Ate Pairing
Chang-An Zhao, Fangguo Zhang, Jiwu Huang
The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius $t$. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as $r^{1/\varphi(k)}$ on more pairing-friendly curves generated by the method...
Efficient Pairing Computation on Curves
Rongquan Feng, Hongfeng Wu
In this paper, a method for the efficient computation of Tate
pairings on curves which is a generalization of Barreto, etc.'s
method [2] is presented. It can reduce the number of
loops in the computation of the Tate pairing. The method can be
applied not only to supersingular curves but to non-supersingular
curves. An example shows the cost of the algorithm in this paper can
be reduced by 18% than the best known algorithm in some elliptic
curves.
Optimised versions of the Ate and Twisted Ate Pairings
Seiichi Matsuda, Naoki Kanayama, Florian Hess, Eiji Okamoto
Foundations
The Ate pairing and the twisted Ate pairing for ordinary elliptic curves
which are generalizations of the $\eta_T$ pairing for supersingular curves have previously been proposed.
It is not necessarily the case that both pairings are faster than the Tate pairing.
In this paper we propose optimized versions of the Ate and twisted Ate pairings with the loop reduction method and show that both pairings are always at least as fast as the Tate pairing.
We also provide suitable families of elliptic...
Side Channel Analysis of Practical Pairing Implementations: Which Path is More Secure?
Claire Whelan, Mike Scott
We present an investigation into the security of three practical pairing algorithms; the Tate, Eta and Ate pairing, in terms of side
channel vulnerability. These three algorithms have recently shown to be efficiently computable on the resource constrained smart card, yet no in depth side channel analysis has yet appeared in the literature. Since the secret parameter input to the pairing can potentially be entered in either of the two possible positions, there exist two avenues of attack,...
Ate pairing for $y^{2}=x^{5}-\alpha x$ in characteristic five
Ryuichi Harasawa, Yutaka Sueyoshi, Aichi Kudo
Recently, the authors proposed a method for computing the Tate pairing using a distortion map for $y^{2}=x^{5} -\alpha x$
($\alpha = \pm2$) over finite fields of characteristic five.
In this paper, we show the Ate pairing, an invariant of the Tate pairing, can be applied to this curve.
This leads to about $50\%$ computational cost-saving
over the Tate pairing.
On Computing Products of Pairings
R Granger, N. P. Smart
Implementation
In many pairing-based protocols often the evaluation of the product
of many pairing evaluations is required. In this paper we consider
methods to compute such products efficiently. Focusing on pairing-friendly fields
in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms
for ordinary elliptic curves at various security levels. Our operation counts
indicate that the minimal cost of each additional pairing relative to the cost of
one is $\approx 0.61$, $0.45$, and...
Implementing Cryptographic Pairings on Smartcards
Michael Scott, Neil Costigan, Wesam Abdulwahab
Implementation
Pairings on elliptic curves are fast coming of age as cryptographic primitives for deployment in new security applications, particularly in the context of implementations of Identity-Based Encryption (IBE). In this paper we describe the implementation of various pairings on a contemporary 32-bit smart-card, the Philips Hi{P}er{S}mart\texttrademark , an instantiation of the MIPS-32 based Smart{MIPS}\texttrademark architecture. Three types of pairing are considered, first the standard Tate...
For many pairing-based cryptographic protocols such as Direct Anonymous Attestation (DAA) schemes, the arithmetic on the first pairing subgroup $\mathbb{G}_1$ is more fundamental. Such operations heavily depend on the sizes of prime fields. At the 192-bit security level, Gasnier and Guillevic presented a curve named GG22D7-457 with CM-discriminant $D = 7$ and embedding degree $k = 22$. Compared to other well-known pairing-friendly curves at the same security level, the curve GG22D7-457 has...
Since the advent of pairing based cryptography, many researchers have developed several techniques and variants of pairings to optimise the speed of pairing computations. The selection of the elliptic curve for a given pairing based protocol is crucial for operations in the first and second pairing groups of points of the elliptic curve and for many cryptographic schemes. A new variant of superoptimal pairing was proposed in 2023, namely x-superoptimal pairing on curves with odd prime...
Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, \ldots, pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions. This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt...
Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the...
The choice of the elliptic curve for a given pairing based protocol is primordial. For many cryptosystems based on pairings such as group signatures and their variants (EPID, anonymous attestation, etc) or accumulators, operations in the first pairing group $\mathbb{G}$ of points of the elliptic curve is more predominant. At $128$-bit security level two curves $BW13-P310$ and $BW19-P286$ with odd embedding degrees $13$ and $19$ suitable for super optimal pairing have been recommended for...
We propose a novel approach that generalizes interleaved modular multiplication algorithms for the computation of sums of products over large prime fields. This operation has widespread use and is at the core of many cryptographic applications. The method reformulates the widely used lazy reduction technique, crucially avoiding the need for storage and computation of "double-precision" operations. Moreover, it can be easily adapted to the different methods that exist to compute modular...
At CANS’20, El Housni and Guillevic introduced a new 2-chain of pairing-friendly elliptic curves for recursive zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARKs) made of the former BLS12-377 curve (a Barreto–Lynn–Scott curve over a 377- bit prime field) and the new BW6-761 curve (a Brezing–Weng curve of embedding degree 6 over a 761-bit prime field). First we generalise the curve construction, the pairing formulas (e : G1 × G2 → GT ) and the group operations to any...
Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy...
Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...
The final exponentiation, which is the exponentiation by a fixed large exponent, must be performed in the Tate and (optimal) Ate pairing computation to ensure output uniqueness, algorithmic correctness, and security for pairing-based cryptography. In this paper, we propose a new framework of efficient final exponentiation for pairings over families of elliptic curves. Our framework provides two methods: the first method supports families of elliptic curves with arbitrary embedding degrees,...
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
Recent algorithmic improvements of discrete logarithm computation in special extension fields threaten the security of pairing-friendly curves used in practice. A possible answer to this delicate situation is to propose alternative curves that are immune to these attacks, without compromising the efficiency of the pairing computation too much. We follow this direction, and focus on embedding degrees 5 to 8; we extend the Cocks-Pinch algorithm to obtain pairing-friendly curves with an...
Internet of Things (IoT) have seen tremendous growth and are being deployed pervasively in areas such as home, surveillance, health-care and transportation. These devices collect and process sensitive data with respect to user's privacy. Protecting the privacy of the user is an essential aspect of security, and anonymous attestation of IoT devices are critical to enable privacy-preserving mechanisms. Enhanced Privacy ID (EPID) is an industry-standard cryptographic scheme that offers...
This paper presents efficient formulas to compute Miller doubling and Miller addition utilizing degree-3 twists on curves with j-invariant 0 written in Hessian form. We give the formulas for both odd and even embedding degrees and for pairings on both $\mathbb{G}_1\times\mathbb{G}_2$ and $\mathbb{G}_2\times\mathbb{G}_1$. We propose the use of embedding degrees 15 and 21 for 128-bit and 192-bit security respectively in light of the NFS attacks and their variants. We give a comprehensive...
In a public-key threshold encryption scheme, the sender produces a single ciphertext, and any $t+1$ out of $n$ intended recipients can combine their partial decryptions to obtain the plaintext. Ad hoc threshold encryption (ATE) schemes require no correlated setup, enabling each party to simply generate its own key pair. In this paper, we initiate a systematic study of the possibilities and limitations of ad-hoc threshold encryption, and introduce a key application to scalable multiparty...
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and...
Much attention has been given to efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The existing few works in the case of odd embedding degrees require some improvements. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9, 15 \mbox{ and } 27$ which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower...
Many pairing-based protocols require the computation of the product and/or of a quotient of n pairings where n > 1 is a natural integer. Zhang et al.[1] recently showed that the Kachisa-Schafer and Scott family of elliptic curves with embedding degree 16 denoted KSS16 at the 192-bit security level is suitable for such protocols comparatively to the Baretto- Lynn and Scott family of elliptic curves of embedding degree 12 (BLS12). In this work, we provide important corrections and improvements...
Barreto, Lynn and Scott elliptic curves of embedding degree 12 denoted BLS12 have been proven to present fastest results on the implementation of pairings at the 192-bit security level [1]. The computation of pairings in general involves the execution of the Miller algorithm and the final exponentiation. In this paper, we improve the complexity of these two steps up to 8% by searching an appropriate parameter. We compute the optimal ate pairing on BLS curves of embedding degree 12 and we...
To have an efficient asymmetric key encryption scheme such as elliptic curves, hyperelliptic curves, pairing etc., we have to go through an arithmetic optimization then a hardware one. Taking into consideration restricted environments’ compromises, we should strike a balance between efficiency and memory resources. For this reason, we studied the mathematical aspect of pairing computation and gave new development of the methods that compute the hard part of the final exponentiation in [2]....
The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special `easy' cases or even showed that...
This paper proposes the computation of the Tate pairing, Ate pairing and its variations on the special Jacobi quartic elliptic curve Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller's algorithm to compute the Tate pairing. We use the birational equivalence between Jacobi quartic curves and Weierstrass curves, together with a specific point representation to obtain the best result to date among curves with quartic twists. For the doubling and addition steps in...
Self-pairings are a special subclass of pairings and have interesting applications in cryptographic schemes and protocols. In this paper, we explore the computation of the self-pairings on supersingular elliptic curves with embedding degree $k = 3$. We construct a novel self-pairing which has the same Miller loop as the Eta/Ate pairing. However, the proposed self-pairing has a simple final exponentiation. Our results suggest that the proposed self-pairings are more efficient than the other...
The hyperelliptic curve Ate pairing provides an efficient way to compute a bilinear pairing on the Jacobian variety of a hyperelliptic curve. We prove that, for supersingular elliptic curves with embedding degree two, square of the Ate pairing is nothing but the Weil pairing. Using the formula, we develop an X-coordinate only pairing inversion method. However, the algorithm is still infeasible for cryptographic size problems.
Broadcast encryption is conventionally formalized as broadcast encapsulation in which, instead of a cipher- text, a session key is produced, which is required to be indistinguishable from random. Such a scheme can provide public encryption functionality in combination with a symmetric encryption through the hybrid en- cryption paradigm. The Boneh-Gentry-Waters scheme of 2005 proposed a broadcast scheme with constant-size ciphertext. It is one of the most efficient broadcast encryption...
We present an efficient implementation of the Optimal Ate Pairing on Barreto-Naehrig curve over a 254-bit prime field on Intel Haswell processor. Our library is able to compute the optimal ate pairing over a 254-bit prime field, in just 1.17 million of clock cycles on a single core of an Intel Core i7-4700MQ(2.4GHz) processor with TurboBoost technology disabled.
The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem(PI). In this paper, we discuss the difficulty of pairing inversion on the generalized ate pairings of Vercauteren. First, we provide a simpler approach for PI by generalizing and simplifying Kanayama-Okamoto’s approach; our approach involves modifications of exponentiation inversion(EI) and Miller inversion(MI), via an “auxiliary” pairing. Then we provide a...
We provide software implementation timings for pairings over composite-order and prime-order elliptic curves. Composite orders must be large enough to be infeasible to factor. They are modulus of 2 up to 5 large prime numbers in the literature. There exists size recommendations for two-prime RSA modulus and we extend the results of Lenstra concerning the RSA modulus sizes to multi-prime modulus, for various security levels. We then implement a Tate pairing over a composite order...
In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we...
At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates. On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in...
Let $E$ be an elliptic curve over a finite field ${\mathbb F}_q$ with a power of prime $q$, $r$ a prime dividing $\#E({\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r | \Phi_k(p)$, called embedding degree. Then a bilinear map $t: E({\mathbb F}_q)[r] \times E({\mathbb F}_{q^k})/rE({\mathbb F}_{q^k}) \rightarrow {\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. And the Ate pairing and other variants are obtained by reducing the domain for each argument and raising...
As hardware capabilities increase, low-power devices such as smartphones represent a natural environment for the efficient implementation of cryptographic pairings. Few works in the literature have considered such platforms despite their growing importance in a post-PC world. In this paper, we investigate the efficient computation of the Optimal-Ate pairing over Barreto-Naehrig curves in software at different security levels on ARM processors. We exploit state-of-the-art techniques and...
In implementation of elliptic curve cryptography, three kinds of finite fields have been widely studied, i.e. prime field, binary field and optimal extension field. In pairing-based cryptography, however, pairing-friendly curves are usually chosen among ordinary curves over prime fields and supersingular curves over extension fields with small characteristics. In this paper, we study pairings on elliptic curves over extension fields from the point of view of accelerating the Miller's...
We complete the study of [23] and [27] about Miller's algorithm. Miller's algorithm is a central step to compute the Weil, Tate and Ate pairings. The aim of this article is to analyze the weakness of Miller's algorithm when it undergoes a fault attack. We prove that Miller's algorithm is vulnerable to a fault attack which is valid in all coordinate systems, through the resolution of a nonlinear system. We highlight the fact that putting the secret as the rst argument of the pairing is not a...
Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfamilies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations. Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific...
In this paper, we present a high speed pairing coprocessor using Residue Number System (RNS) and lazy reduction. We show that combining RNS, which are naturally suitable for parallel architectures, and lazy reduction, which performs one reduction for more than one multiplication, the computational complexity of pairings can be largely reduced. The design is prototyped on a Xilinx Virtex-6 FPGA, which utilizes 7023 slices and 32 DSPs, and finishes one 254-bit optimal ate pairing computation...
Pairings on elliptic curves are being used in an increasing number of cryptographic applications on many different devices and platforms, but few performance numbers for cryptographic pairings have been reported on embedded and mobile devices. In this paper we give performance numbers for affine and projective pairings on a dual-core Cortex A9 ARM processor and compare performance of the same implementation across three platforms: x86, x86-64 and ARM. Using a fast inversion in the base...
For the last decade, elliptic curve cryptography has gained increasing interest in industry and in the academic community. This is especially due to the high level of security it provides with relatively small keys and to its ability to create very efficient and multifunctional cryptographic schemes by means of bilinear pairings. Pairings require pairing-friendly elliptic curves and among the possible choices, Barreto-Naehrig (BN) curves arguably constitute one of the most versatile...
In this paper we analyze the use of affine coordinates for pairing computation. We observe that in many practical settings, for example when implementing optimal ate pairings in high security levels, affine coordinates are faster than using the best currently known formulas for projective coordinates. This observation relies on two known techniques for speeding up field inversions which we analyze in the context of pairing computation. We give detailed performance numbers for a pairing...
This paper describes the design of a fast software library for the computation of the optimal ate pairing on a Barreto--Naehrig elliptic curve. Our library is able to compute the optimal ate pairing over a $254$-bit prime field $\mathbb{F}_{p}$, in just $2.63$ million of clock cycles on a single core of an Intel Core i7 $2.8$GHz processor, which implies that the pairing computation takes $0.942$msec. We are able to achieve this performance by a careful implementation of the base field...
In 2007, Stange proposed a novel method of computing the Tate pairing on an elliptic curve over a finite field. This method is based on elliptic nets, which are maps from $\mathbb{Z}^n$ to a ring that satisfy a certain recurrence relation. In this paper, we explicitly give formulae for computing some variants of the Tate pairing: Ate, Ate$_i$, R-Ate and Optimal pairings, based on elliptic nets. We also discuss their efficiency by using some experimental results.
A common scenario in many pairing-based cryptographic protocols is that one argument in the pairing is fixed as a long term secret key or a constant parameter in the system. In these situations, the runtime of Miller’s algorithm can be significantly reduced by storing precomputed values that depend on the fixed argument, prior to the input or existence of the second argument. In light of recent developments in pairing computation, we show that the computation of the Miller...
This paper presents new software speed records for the computation of cryptographic pairings. More specifically, we present details of an implementation which computes the optimal ate pairing on a 256-bit Barreto-Naehrig curve in only 4,379,912 cycles on one core of an Intel Core 2 Quad Q9550 processor. This speed is achieved by combining 1.) state-of-the-art high-level optimization techniques, 2.) a new representation of elements in the underlying finite fields which makes use of the...
Miller's algorithm for computing pairings involves performing multiplications between elements that belong to different finite fields. Namely, elements in the full extension field $\mathbb{F}_{p^k}$ are multiplied by elements contained in proper subfields $\mathbb{F}_{p^{k/d}}$, and by elements in the base field $\mathbb{F}_{p}$. We show that significant speedups in pairing computations can be achieved by delaying these ``mismatched'' multiplications for an optimal number of iterations....
The most costly operations encountered in pairing computations are those that take place in the full extension field $\mathbb{F}_{p^k}$. At high levels of security, the complexity of operations in $\mathbb{F}_{p^k}$ dominates the complexity of the operations that occur in the lower degree subfields. Consequently, full extension field operations have the greatest effect on the runtime of Miller's algorithm. Many recent optimizations in the literature have focussed on improving the overall...
We need to perform arithmetic in $\Fpt$ to use Ate pairing on a Barreto-Naehrig (BN) curve, where $p(z)$ is a prime given by $p(z)=36z^4+36z^3+24z^2+6z+1$ with an integer $z$. In many implementations of Ate pairing, $\Fpt$ has been regarded as the 6-th extension of $\Fpp$, and it has been constructed as $\Fpt=\Fpp[v]/(v^6-\xi)$ for an element $\xi\in \Fpp$ such that $v^6-\xi$ is irreducible in $\Fpp[v]$. Such $\xi$ depends on the value of $p(z)$, and we may use mathematic software to find...
Research on efficient pairing implementation has focussed on reducing the loop length and on using high-degree twists. Existence of twists of degree larger than $2$ is a very restrictive criterion but luckily constructions for pairing-friendly elliptic curves with such twists exist. In fact, Freeman, Scott and Teske showed in their overview paper that often the best known methods of constructing pairing-friendly elliptic curves over fields of large prime characteristic produce curves that...
Vercauteren introduced a notion of optimal pairings. Up to know the only known optimal pairing is the optimal Ate pairing. In this paper, we give some properties of optimal pairing and provide an algorithm for finding an optimal pairing if there exists one which is defined on the given elliptic curve. Applying the cyclotomic polynomial, we construct some new optimal pairings and provide a construction method of pairing-friendly elliptic curves on which the optimal pairing can be defined....
This paper presents the first study of pairing computation on curves with embedding degree $15$. We compute the Ate and the twisted Ate pairing for a family of curves with parameter $\rho~1.5$ and embedding degree $15$. We use a twist of degree 3 to perform most of the operations in $\F_p$ or $\F_{p^5}$. Furthermore, we present a new arithmetic for extension fields of degree $5$. Our computations show that these curves give very efficient implementations for pairing-based cryptography at...
In this paper we show an efficient implementation if the Tate, ate, and R-ate pairings in magma. This will be demostrated by using the KSS curves with embedding degree k=18
This paper presents a design-space exploration of an application-specific instruction-set processor (ASIP) for the computation of various cryptographic pairings over Barreto-Naehrig curves (BN curves). Cryptographic pairings are based on elliptic curves over finite fields--in the case of BN curves a field Fp of large prime order p. Efficient arithmetic in these fields is crucial for fast computation of pairings. Moreover, computation of cryptographic pairings is much more complex than...
When using pairing-friendly ordinary elliptic curves to compute the Tate and related pairings, the computation consists of two main components, the Miller loop and the so-called final exponentiation. As a result of good progress being made to reduce the Miller loop component of the algorithm (particularly with the discovery of ``truncated loop'' pairings like the R-ate pairing), the final exponentiation has become a more significant component of the overall calculation. Here we exploit the...
In this paper we show that the twisted Ate pairing on elliptic curves can be generalized to hyperelliptic curves, we also give a series of variations of the hyperelliptic Ate and twisted Ate pairings. Using the hyperelliptic Ate pairing and twisted Ate pairing, we propose a new approach to speed up the Weil pairing computation, and obtain an interested result: For some hyperelliptic curves with high degree twist, using this approach to compute Weil pairing will be faster than Tate pairing,...
In this paper, we present some new variants based on the Weil pairing for efficient pairing computations. The new pairing variants have the short Miller iteration loop and simple final exponentiation. We then show that computing the proposed pairings is more efficient than computing the Weil pairing. Experimental results for these pairings are also given.
The irreducible factor $r(x)$ of $\mathrm{\Phi}_{k}(u(x))$ and $u(x) $ are often used in constructing pairing-friendly curves. $u(x)$ and $u_{c} \equiv u(x)^{c} \pmod{r(x)}$ are selected to be the Miller loop control polynomial in Ate pairing and $\mathrm{Ate}_{i}$ pairing. In this paper we show that when $4|k$ or the minimal prime which divides $k$ is larger than $2$, some $u(x)$ and $r(x)$ can not be used as curve generation parameters if we want $\mathrm{Ate}_{i}$ pairing to be efficient....
In this paper we introduce the concept of an \emph{optimal pairing}, which by definition can be computed using only $\log_2 r/ \varphi(k)$ basic Miller iterations, with $r$ the order of the groups involved and $k$ the embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any non-degenerate pairing on an elliptic curve without efficiently computable endomorphisms different...
In this paper, we suggest that all pairings be in a group from an abstract angle. It is possible that our observation can be applied into other aspects of pairing-based cryptosystems.
In this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the R-ate pairing. This pairing is a generalization of the Ate and Ate_i pairing, and also improves efficiency of the pairing computation. Using the R-ate pairing, the loop length in Miller's algorithm can be as small as ${\rm log}(r^{1 / \phi(k)})$ for some pairing-friendly elliptic curves which have not reached this lower bound. Therefore we obtain from 29 % to 69 % savings...
To reduce bandwidth in elliptic curve cryptography one can transmit only $x$-coordinates of points (or $x$-coordinates together with an extra bit). For further computation using the points one can either recover the $y$-coordinates by taking square roots or one can use point multiplication formulae which use $x$-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography. We give a method to compute compressed Weil pairings using $x$-coordinates...
We describe a new method for constructing Brezing-Weng-like pairing-friendly elliptic curves. The new construction uses the minimal polynomials of elements in a cyclotomic field. Using this new construction we present new ``record breaking'' families of pairing-friendly curves with embedding degrees of $k \in \{16,18,36,40\}$, and some interesting new constructions for the cases $k \in \{8,32\}$
For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with $k=9$ or curves with $k=12$. The case $k=9$ has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the $k=9$ case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and...
In this paper we provide explicit formul\ae\ to compute bilinear pairings in compressed form. We indicate families of curves where the proposed compressed computation method can be applied and where particularly generalized versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. Our approach introduces more flexibility when trading off computation speed and memory requirement. Furthermore, compressed computation of reduced pairings can be done without any...
In this paper, we will describe efficient implementations of the Tate and Ate pairings over ordinary elliptic curves of embedding degrees 8 and 10. We will discuss the possible curve-dependent optimizations that can be applied to evaluate the pairings. We pay particular attention to the use of elliptic curve twists and the denominator elimination method to make computations more efficient. Our main goal is to draw together the best possible optimizations that can be used to efficiently...
In this paper we describe an efficient implementation of the Tate and Ate pairings using Barreto-Naehrig pairing-friendly curves, on both a standard 32-bit PC and on a 32-bit smartcard. First we introduce a sub-family of such curves with a particularly simple representation. Next we consider the issues that arise in the efficient implementation of field arithmetic in $\F_{p^{12}}$, which is crucial to good performance. Various optimisations are suggested, including a novel approach to the...
The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius $t$. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as $r^{1/\varphi(k)}$ on more pairing-friendly curves generated by the method...
In this paper, a method for the efficient computation of Tate pairings on curves which is a generalization of Barreto, etc.'s method [2] is presented. It can reduce the number of loops in the computation of the Tate pairing. The method can be applied not only to supersingular curves but to non-supersingular curves. An example shows the cost of the algorithm in this paper can be reduced by 18% than the best known algorithm in some elliptic curves.
The Ate pairing and the twisted Ate pairing for ordinary elliptic curves which are generalizations of the $\eta_T$ pairing for supersingular curves have previously been proposed. It is not necessarily the case that both pairings are faster than the Tate pairing. In this paper we propose optimized versions of the Ate and twisted Ate pairings with the loop reduction method and show that both pairings are always at least as fast as the Tate pairing. We also provide suitable families of elliptic...
We present an investigation into the security of three practical pairing algorithms; the Tate, Eta and Ate pairing, in terms of side channel vulnerability. These three algorithms have recently shown to be efficiently computable on the resource constrained smart card, yet no in depth side channel analysis has yet appeared in the literature. Since the secret parameter input to the pairing can potentially be entered in either of the two possible positions, there exist two avenues of attack,...
Recently, the authors proposed a method for computing the Tate pairing using a distortion map for $y^{2}=x^{5} -\alpha x$ ($\alpha = \pm2$) over finite fields of characteristic five. In this paper, we show the Ate pairing, an invariant of the Tate pairing, can be applied to this curve. This leads to about $50\%$ computational cost-saving over the Tate pairing.
In many pairing-based protocols often the evaluation of the product of many pairing evaluations is required. In this paper we consider methods to compute such products efficiently. Focusing on pairing-friendly fields in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms for ordinary elliptic curves at various security levels. Our operation counts indicate that the minimal cost of each additional pairing relative to the cost of one is $\approx 0.61$, $0.45$, and...
Pairings on elliptic curves are fast coming of age as cryptographic primitives for deployment in new security applications, particularly in the context of implementations of Identity-Based Encryption (IBE). In this paper we describe the implementation of various pairings on a contemporary 32-bit smart-card, the Philips Hi{P}er{S}mart\texttrademark , an instantiation of the MIPS-32 based Smart{MIPS}\texttrademark architecture. Three types of pairing are considered, first the standard Tate...