International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Maria Corte-Real Santos

Publications

Year
Venue
Title
2024
PKC
An algorithm for efficient detection of (N,N)-splittings and its application to the isogeny problem in dimension 2
Maria Corte-Real Santos Craig Costello Sam Frengley
We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally (N,N)-split for each integer N <=11. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime p is 100 bits, the attack is sped up by a factor 25x; when the underlying prime is 200 bits, the attack is sped up by a factor 42x; and, when the underlying prime is 1000 bits, the attack is sped up by a factor 160x.
2024
EUROCRYPT
AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing
We optimise the verification of the SQIsign signature scheme. By using field extensions in the signing procedure, we are able to significantly increase the amount of available rational 2-power torsion in verification, which achieves a significant speed-up. This, moreover, allows several other speed-ups on the level of curve arithmetic. We show that the synergy between these high-level and low-level improvements gives significant improvements, making verification 2.07 times faster, or up to 3.41 times when using size-speed trade-offs, compared to the state of the art, without majorly degrading the performance of signing.
2023
ASIACRYPT
Cryptographic Smooth Neighbors
We revisit the problem of finding two consecutive $B$-smooth integers by giving an optimised implementation of the Conrey-Holm\-strom-McLaughlin ``smooth neighbors'' algorithm. While this algorithm is not guaranteed to return the complete set of $B$-smooth neighbors, in practice it returns a very close approximation to the complete set but does so in a tiny fraction of the time of its exhaustive counterparts. We exploit this algorithm to find record-sized solutions to the pure twin smooth problem, and subsequently to produce instances of cryptographic parameters whose corresponding isogeny degrees are significantly smoother than prior works. Our methods seem well-suited to finding parameters for the SQISign signature scheme, especially for instantiations looking to minimize the cost of signature generation. We give a number of examples, among which are the first parameter sets geared towards efficient SQISign instantiations at NIST's security levels III and V.
2022
CRYPTO
Accelerating the Delfs-Galbraith algorithm with fast subfield root detection 📺
Maria Corte-Real Santos Craig Costello Jia Shi
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.