## CryptoDB

### Craig Costello

#### Publications

**Year**

**Venue**

**Title**

2022

CRYPTO

Accelerating the Delfs-Galbraith algorithm with fast subfield root detection
📺
Abstract

We give a new algorithm for finding an isogeny from a given supersingular elliptic curve $E/\F_{p^2}$ to a subfield elliptic curve $E'/\F_p$, which is the bottleneck step of the Delfs-Galbraith algorithm for the general supersingular isogeny problem. Our core ingredient is a novel method of rapidly determining whether a polynomial $f \in L[X]$ has any roots in a subfield $K \subset L$, while avoiding expensive root-finding algorithms. In the special case when $f=\Upphi_{\ell,p}(X,j) \in \F_{p^2}[X]$, i.e., when $f$ is the $\ell$-th modular polynomial evaluated at a supersingular $j$-invariant, this provides a means of efficiently determining whether there is an $\ell$-isogeny connecting the corresponding elliptic curve to a subfield curve. Together with the traditional Delfs-Galbraith walk, inspecting many $\ell$-isogenous neighbours in this way allows us to search through a larger proportion of the supersingular set per unit of time. Though the asymptotic $\tilde{O}(p^{1/2})$ complexity of our improved algorithm remains unchanged from that of the original Delfs-Galbraith algorithm, our theoretical analysis and practical implementation both show a significant reduction in the runtime of the subfield search. This sheds new light on the concrete hardness of the general supersingular isogeny problem (i.e. the foundational problem underlying isogeny-based cryptography), and has immediate implications on the bit-security of schemes like B-SIDH and SQISign for which Delfs-Galbraith is the best known classical attack.

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

#### Program Committees

- PKC 2022
- Asiacrypt 2022
- Crypto 2020
- PKC 2019

#### Coauthors

- Lejla Batina (1)
- Joppe W. Bos (4)
- Maria Corte-Real Santos (1)
- Hüseyin Hisil (1)
- Hüseyin Hisil (6)
- David Jao (1)
- Tanja Lange (1)
- Kristin E. Lauter (3)
- Patrick Longa (4)
- Michael Meyer (1)
- Andrea Miele (1)
- Michael Naehrig (5)
- Joost Renes (3)
- Jia Shi (1)
- Benjamin Smith (1)
- David Urbanik (1)
- Fernando Virdia (1)