## CryptoDB

### Craig Costello

#### Affiliation: Microsoft Research

#### 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

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.

2020

ASIACRYPT

B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
📺
Abstract

This paper explores a new way of instantiating isogeny-based cryptography in which parties can work in both the (p+1)-torsion of a set of supersingular curves and in the (p-1)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF(p^2) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF(p^2) as usual. Furthermore, since supersingular twists always have the same GF(p^2)-rational j-invariant, the SIDH protocol remains unchanged when Alice and Bob are free to work in both sets of twists.
This framework lifts the restrictions on the shapes of the underlying prime fields originally imposed by Jao and De Feo, and allows a range of new options for instantiating isogeny-based public key cryptography. These include alternatives that exploit Mersenne and Montgomery-friendly primes, as well as the possibility of halving the size of the primes in the Jao-De Feo construction at no known loss of asymptotic security. For a given target security level, the resulting public keys are smaller than the public keys of all of the key encapsulation schemes currently under consideration in the NIST post-quantum standardisation effort.
The best known attacks against the instantiations proposed in this paper are the classical path finding algorithm due to Delfs and Galbraith and its quantum adapation due to Biasse, Jao and Sankar; these run in respective time O(p^(1/2)) and O(p^(1/4)), and are essentially memory-free. The upshot is that removing the big-O's and obtaining concrete security estimates is a matter of costing the circuits needed to implement the corresponding isogeny. In contrast to other post-quantum proposals, this makes the security analysis of B-SIDH rather straightforward.
Searches for friendly parameters are used to find several primes that range from 237 to 256 bits, the conjectured security of which are comparable to the 434-bit prime used to target NIST level 1 security in the SIKE proposal. One noteworthy example is a 247-bit prime for which Alice's secret isogeny is 7901-smooth and Bob's secret isogeny is 7621-smooth.

2018

ASIACRYPT

Computing Supersingular Isogenies on Kummer Surfaces
Abstract

We apply Scholten’s construction to give explicit isogenies between the Weil restriction of supersingular Montgomery curves with full rational 2-torsion over $$\mathbb {F}_{p^2}$$ and corresponding abelian surfaces over $$\mathbb {F}_{p}$$. Subsequently, we show that isogeny-based public key cryptography can exploit the fast Kummer surface arithmetic that arises from the theory of theta functions. In particular, we show that chains of 2-isogenies between elliptic curves can instead be computed as chains of Richelot (2, 2)-isogenies between Kummer surfaces. This gives rise to new possibilities for efficient supersingular isogeny-based cryptography.

2015

ASIACRYPT

2014

EPRINT

2010

EPRINT

Avoiding Full Extension Field Arithmetic in Pairing Computations
Abstract

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 operation count by presenting new explicit formulas that reduce the number of subfield operations encountered throughout an iteration of Miller's algorithm. Unfortunately, almost all of these operations far outweigh the operations in the smaller subfields. In this paper, we propose a new way of carrying out Miller's algorithm that involves new explicit formulas which reduce the number of full extension field operations that occur in an iteration of the Miller loop, resulting in significant speed ups in most practical situations of between 5 and 30 percent.

2010

EPRINT

Delaying Mismatched Field Multiplications in Pairing Computations
Abstract

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. Importantly, we show that our technique can be easily integrated into traditional pairing algorithms; implementers can exploit the computational savings herein by applying only minor changes to existing pairing code.

2010

EPRINT

Fixed Argument Pairings
Abstract

A common scenario in many pairing-based cryptographic protocols is that one argument in the pairing is ﬁxed as a long term secret key or a constant parameter in the system. In these situations, the runtime of Millers algorithm can be signiﬁcantly reduced by storing precomputed values that depend on the ﬁxed 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 loop can be sped up by up to 37% if precomputation is employed, with our method being up to 19.5% faster than the previous precomputation techniques.

#### Program Committees

- Crypto 2020
- PKC 2019

#### Coauthors

- Paulo S. L. M. Barreto (1)
- Lejla Batina (2)
- Joppe W. Bos (6)
- Colin Boyd (2)
- Ping Ngai Chung (1)
- Alyson Deines-Schartz (1)
- C. C. F. Pereira Geovandro (1)
- Hüseyin Hisil (1)
- Hüseyin Hisil (7)
- David Jao (1)
- Tanja Lange (1)
- Kristin E. Lauter (4)
- Patrick Longa (6)
- Michael Meyer (1)
- Andrea Miele (1)
- Rafael Misoczki (1)
- Michael Naehrig (8)
- Juan Manuel González Nieto (2)
- Joost Renes (4)
- Benjamin Smith (2)
- Douglas Stebila (2)
- David Urbanik (1)
- Fernando Virdia (1)
- Kenneth Koon-Ho Wong (2)
- Tonghai Yang (1)
- Gustavo Zanon (1)