## CryptoDB

### Michael Naehrig

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Sieving for twin smooth integers with solutions to the Prouhet-Tarry-Escott problem
Abstract

We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Any such solution induces two degree-n polynomials, a(x) and b(x), that differ by a constant integer C and completely split into linear factors in Z[x]. It follows that for any l in Z such that a(l) = b(l) = 0 mod C , the two integers a(l)/C and b(l)/C differ by 1 and necessarily contain n factors of roughly the same size. For a fixed smoothness bound B, restricting the search to pairs of integers that are parameterized in this way increases the probability that they are B-smooth. Our algorithm combines a simple sieve with parametrizations given by a collection of solutions to the PTE problem.
The motivation for finding large twin smooth integers lies in their application to compact isogeny-based post-quantum protocols. The recent key exchange scheme B-SIDH and the recent digital signature scheme SQISign both require large primes that lie between two smooth integers; finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime p.
When searching for cryptographic parameters with 2^240 <= p < 2^256, an implementation of our sieve found primes p where p+1 and p-1 are 2^15-smooth; the smoothest prior parameters had a similar sized prime for which p-1 and p+1 were 2^19-smooth. In targeting higher security levels, our sieve found a 376-bit prime lying between two 2^21-smooth integers, a 384-bit prime lying between two 2^22-smooth integers, and a 512-bit prime lying between two 2^29-smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.

2020

EUROCRYPT

Implementing Grover oracles for quantum key search on AES and LowMC
📺
Abstract

Grover's search algorithm gives a quantum attack against block ciphers by searching for a key that matches a small number of plaintext-ciphertext pairs. This attack uses O(N) calls to the cipher to search a key space of size N. Previous work in the specific case of AES derived the full gate cost by analyzing quantum circuits for the cipher, but focused on minimizing the number of qubits.
In contrast, we study the cost of quantum key search attacks under a depth restriction and introduce techniques that reduce the oracle depth, even if it requires more qubits. As cases in point, we design quantum circuits for the block ciphers AES and LowMC. Our circuits give a lower overall attack cost in both the gate count and depth-times-width cost models. In NIST's post-quantum cryptography standardization process, security categories are defined based on the concrete cost of quantum key search against AES. We present new, lower cost estimates for each category, so our work has immediate implications for the security assessment of post-quantum cryptography.
As part of this work, we release Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates. To the best of our knowledge, these are the first two such full implementations and automatic resource estimations.

2020

PKC

Improved Classical Cryptanalysis of SIKE in Practice
📺
Abstract

The main contribution of this work is an optimized implementation of the van Oorschot-Wiener (vOW) parallel collision finding algorithm. As is typical for cryptanalysis against conjectured hard problems (e. g. factoring or discrete logarithms), challenges can arise in the implementation that are not captured in the theory, making the performance of the algorithm in practice a crucial element of estimating security. We present a number of novel improvements, both to generic instantiations of the vOW algorithm finding collisions in arbitrary functions, and to its instantiation in the context of the supersingular isogeny key encapsulation (SIKE) protocol, that culminate in an improved classical cryptanalysis of the computational supersingular isogeny (CSSI) problem. In particular, we present a scalable implementation that can be applied to the Round-2 parameter sets of SIKE that can be used to give confidence in their security levels.

2019

ASIACRYPT

Dual Isogenies and Their Application to Public-Key Compression for Isogeny-Based Cryptography
Abstract

The isogeny-based protocols SIDH and SIKE have received much attention for being post-quantum key agreement candidates that retain relatively small keys. A recent line of work has proposed and further improved compression of public keys, leading to the inclusion of public-key compression in the SIKE proposal for Round 2 of the NIST Post-Quantum Cryptography Standardization effort. We show how to employ the dual isogeny to significantly increase performance of compression techniques, reducing their overhead from 160–182% to 77–86% for Alice’s key generation and from 98–104% to 59–61% for Bob’s across different SIDH parameter sets. For SIKE, we reduce the overhead of (1) key generation from 140–153% to 61–74%, (2) key encapsulation from 67–90% to 38–57%, and (3) decapsulation from 59–65% to 34–39%. This is mostly achieved by speeding up the pairing computations, which has until now been the main bottleneck, but we also improve (deterministic) basis generation.

2014

EPRINT

2010

EPRINT

New software speed records for cryptographic pairings
Abstract

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
Abstract

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
Abstract

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.

2008

EPRINT

CM construction of genus 2 curves with p-rank 1
Abstract

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
Abstract

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
Abstract

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

#### Coauthors

- Paulo S. L. M. Barreto (4)
- Joppe W. Bos (3)
- Craig Costello (8)
- Tony Feng (1)
- C. C. F. Pereira Geovandro (1)
- David Jao (1)
- Samuel Jaques (1)
- Marcos A. Simplício Jr (1)
- Tanja Lange (1)
- Kristin E. Lauter (5)
- Tancrède Lepoint (1)
- Patrick Longa (4)
- Adriana López-Alt (1)
- Adrián Macías (2)
- Gary McGuire (1)
- Michael Meyer (1)
- Rafael Misoczki (1)
- Peter L. Montgomery (1)
- Ruben Niederhagen (1)
- Laura Hitt O'Connor (1)
- Geovandro C. C. F. Pereira (1)
- Thomas Pöppelmann (2)
- Andrew Putnam (2)
- Joost Renes (3)
- Martin Roetteler (2)
- Peter Schwabe (1)
- Douglas Stebila (1)
- Marco Streng (1)
- Krysta M. Svore (1)
- David Urbanik (1)
- Fernando Virdia (2)
- David J. Wu (1)
- Gustavo Zanon (1)