International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Michael Naehrig

Affiliation: Microsoft Research

Publications

Year
Venue
Title
2017
EUROCRYPT
2017
ASIACRYPT
2016
CRYPTO
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
CHES
2014
EPRINT
2014
EPRINT
2014
EPRINT
2014
EPRINT
2010
EPRINT
New software speed records for cryptographic pairings
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 special modulus arising from the Barreto-Naehrig curve construction, and 3.) implementing arithmetic in this representation using the double-precision floating-point SIMD instructions of the AMD64 architecture.
2010
EPRINT
An Analysis of Affine Coordinates for Pairing Computation
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 implementation based on these ideas, including timings for base field and extension field arithmetic with relative ratios for inversion-to-multiplication costs, timings for pairings in both affine and projective coordinates, and average timings for multiple pairings and products of pairings.
2010
EPRINT
A Family of Implementation-Friendly BN Elliptic Curves
We describe a class of Barreto-Naehrig (BN) curves that are not only computationally very simple to generate, but also specially suitable for efficient implementation on the broadest possible range of platforms.
2010
PKC
2008
EPRINT
CM construction of genus 2 curves with p-rank 1
We present an algorithm for constructing cryptographic hyperelliptic curves of genus $2$ and $p$-rank $1$, using the CM method. We also present an algorithm for constructing such curves that, in addition, have a prescribed small embedding degree. We describe the algorithms in detail, and discuss other aspects of $p$-rank 1 curves too, including the reduction of the class polynomials modulo $p$.
2007
EPRINT
On compressible pairings and their computation
Michael Naehrig Paulo S. L. M. Barreto
In this paper we provide explicit formulae to compute bilinear pairings in compressed form, and indicate families of curves where particularly generalised versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. With the new formulae it is possible to entirely avoid $\F_{p^k}$ arithmetic during pairing computation on elliptic curves over $\F_p$ with even embedding degree $k$. Using our new method all intermediate results in the Miller loop are represented by just one $\F_{p^{k/2}}$ element and manipulated in compressed form. For certain families of ordinary curves with embedding degree $k = 6m$ all arithmetic can be done in a subfield of size $p^m$ and the representation can be further compressed to two $\F_{p^m}$ elements.
2005
EPRINT
Pairing-Friendly Elliptic Curves of Prime Order
Paulo S. L. M. Barreto Michael Naehrig
Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6$. More general methods produce curves over $\F_p$ where the bit length of $p$ is often twice as large as that of the order $r$ of the subgroup with embedding degree $k$; the best published results achieve $\rho \equiv \log(p)/\log(r) \sim 5/4$. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree $k = 12$. The new curves lead to very efficient implementation: non-pairing cryptosystem operations only need $\F_p$ and $\F_{p^2}$ arithmetic, and pairing values can be compressed to one \emph{sixth} of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants $D$ to minimize $\rho$; in particular, for embedding degree $k = 2q$ where $q$ is prime we show that the ability to handle $\log(D)/\log(r) \sim (q-3)/(q-1)$ enables building curves with $\rho \sim q/(q-1)$.

Program Committees

Crypto 2019
PKC 2015