Accelerating the Delfs-Galbraith algorithm with fast subfield root detection

Опубликовано 26 июля 2022, 18:25

In this talk, we discuss the general supersingular isogeny problem, the foundational hardness assumption underpinning isogeny-based cryptography. We implement and optimize the best attack against this problem – the Delfs-Galbraith algorithm – to explicitly determine its concrete complexity. We then develop an improved algorithm that employs a novel method of rapidly determining whether a polynomial has any roots in a subfield. Our improved attack decreases the concrete complexity by a factor of at least 4, an advantage that increases as the parameters (i.e., the underlying prime p) grow.

As a result, we shed new light on the concrete hardness of the general supersingular isogeny problem, which has immediate implications on the bit-security of schemes like B-SIDH and SQISign for which Delfs–Galbraith is the best-known classical attack.

This is based on joint work with Craig Costello and Jia Shi.