Dates are inconsistent

Dates are inconsistent

16 results sorted by ID

Possible spell-corrected query: dealing correspondence
2025/1154 (PDF) Last updated: 2025-06-18
Evaluation of Modular Polynomials from Supersingular Elliptic Curves
Maria Corte-Real Santos, Jonathan Komada Eriksen, Antonin Leroux, Michael Meyer, Lorenz Panny
Implementation

We present several new algorithms to evaluate modular polynomials of level $\ell$ modulo a prime $p$ on an input $j$. More precisely, we introduce two new generic algorithms, sharing the following similarities: they are based on a CRT approach; they make use of supersingular curves and the Deuring correspondence; and, their memory requirements are optimal. The first algorithm combines the ideas behind a hybrid algorithm of Sutherland in 2013 with a recent algorithm to compute...

2025/372 (PDF) Last updated: 2025-07-01
KLPT²: Algebraic Pathfinding in Dimension Two and Applications
Wouter Castryck, Thomas Decru, Péter Kutas, Abel Laval, Christophe Petit, Yan Bo Ti
Public-key cryptography

Following Ibukiyama, Katsura and Oort, all principally polarized superspecial abelian surfaces over $\overline{\mathbb{F}}_p$ can be represented by a certain type of $2 \times 2$ matrix $g$, having entries in the quaternion algebra $B_{p,\infty}$. We present a heuristic polynomial-time algorithm which, upon input of two such matrices $g_1, g_2$, finds a "connecting matrix" representing a polarized isogeny of smooth degree between the corresponding surfaces. Our algorithm should be thought...

2025/136 (PDF) Last updated: 2025-03-28
Computing Isomorphisms between Products of Supersingular Elliptic Curves
Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer
Public-key cryptography

The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of...

2024/1852 (PDF) Last updated: 2024-11-12
Faster algorithms for isogeny computations over extensions of finite fields
Shiping Cai, Mingjie Chen, Christophe Petit
Public-key cryptography

Any isogeny between two supersingular elliptic curves can be defined over $\mathbb{F}_{p^2}$, however, this does not imply that computing such isogenies can be done with field operations in $\mathbb{F}_{p^2}$. In fact, the kernel generators of such isogenies are defined over extension fields of $\mathbb{F}_{p^2}$, generically with extension degree linear to the isogeny degree. Most algorithms related to isogeny computations are only efficient when the extension degree is small. This leads to...

2024/1225 (PDF) Last updated: 2025-04-04
SIGNITC: Supersingular Isogeny Graph Non-Interactive Timed Commitments
Knud Ahrens
Public-key cryptography

Non-Interactive Timed Commitment schemes (NITC) allow to open any commitment after a specified delay $t_{\mathrm{fd}}$. This is useful for sealed bid auctions and as primitive for more complex protocols. We present the first NITC without repeated squaring or theoretical black box algorithms like NIZK proofs or one-way functions. It has fast verification, almost arbitrary delay and satisfies IND-CCA hiding and perfect binding. Our protocol is based on isogenies between supersingular elliptic...

2024/778 (PDF) Last updated: 2024-12-03
Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
Hiroshi Onuki, Kohei Nakagawa
Public-key cryptography

The Deuring correspondence is a correspondence between supersingular elliptic curves and quaternion orders. Under this correspondence, an isogeny between elliptic curves corresponds to a quaternion ideal. This correspondence plays an important role in isogeny-based cryptography and several algorithms to compute an isogeny corresponding to a quaternion ideal (ideal-to-isogeny algorithms) have been proposed. In particular, SQIsign is a signature scheme based on the Deuring correspondence and...

2024/773 (PDF) Last updated: 2024-10-13
SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies
Max Duparc, Tako Boris Fouotsa
Public-key cryptography

We introduce SQIPrime, a post-quantum digital signature scheme based on the Deuring correspondence and Kani's Lemma. Compared to its predecessors that are SQISign and especially SQISignHD, SQIPrime further expands the use of high dimensional isogenies, already in use in the verification in SQISignHD, to all its subroutines. In doing so, it no longer relies on smooth degree isogenies (of dimension 1). Intriguingly, this includes the challenge isogeny which is also a non-smooth degree...

2024/400 (PDF) Last updated: 2024-07-31
SILBE: an Updatable Public Key Encryption Scheme from Lollipop Attacks
Max Duparc, Tako Boris Fouotsa, Serge Vaudenay
Public-key cryptography

We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalised lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by Fouotsa, Moriya and Petit. Doing so, we can in fact make SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is in fact the first isogeny-based UPKE which is not based on group actions. Hence, SILBE overcomes the...

2023/1537 (PDF) Last updated: 2023-10-20
DEFEND: Towards Verifiable Delay Functions from Endomorphism Rings
Knud Ahrens, Jens Zumbrägel
Cryptographic protocols

We present a verifiable delay function based on isogenies of supersingular elliptic curves, using Deuring correspondence and computation of endomorphism rings for the delay. For each input x a verifiable delay function has a unique output y and takes a predefined time to evaluate, even with parallel computing. Additionally, it generates a proof by which the output can efficiently be verified. In our approach the input is a path in the 2-isogeny graph and the output is the maximal order...

2023/1251 (PDF) Last updated: 2025-02-19
Verifiable random function from the Deuring correspondence and higher dimensional isogenies
Antonin Leroux
Cryptographic protocols

In this paper, we introduce $\mathsf{DeuringVUF}$, a new Verifiable Unpredictable Function (VUF) protocol based on isogenies between supersingular curves. The most interesting application of this VUF is $\mathsf{DeuringVRF}$ a post-quantum Verifiable Random Function (VRF). The main advantage of this new scheme is its compactness, with combined public key and proof size of roughly 450 bytes, which is orders of magnitude smaller than other generic purpose post-quantum VRF...

2023/779 (PDF) Last updated: 2023-09-18
Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH
Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, Christophe Petit
Public-key cryptography

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key...

2023/106 (PDF) Last updated: 2023-08-20
Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic
Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková, Mattia Veroni

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the...

2023/064 (PDF) Last updated: 2023-12-15
Computation of Hilbert class polynomials and modular polynomials from supersingular elliptic curves
Antonin Leroux
Public-key cryptography

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $p$ by revisiting the idea of working with supersingular elliptic curves. The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has...

2022/234 (PDF) Last updated: 2023-04-06
New algorithms for the Deuring correspondence: Towards practical and secure SQISign signatures
Luca De Feo, Antonin Leroux, Patrick Longa, Benjamin Wesolowski
Public-key cryptography

The Deuring correspondence defines a bijection between isogenies of supersingular elliptic curves and ideals of maximal orders in a quaternion algebra. We present a new algorithm to translate ideals of prime-power norm to their corresponding isogenies --- a central task of the effective Deuring correspondence. The new method improves upon the algorithm introduced in 2021 by De Feo, Kohel, Leroux, Petit and Wesolowski as a building-block of the SQISign signature scheme. SQISign is the...

2018/371 (PDF) Last updated: 2018-04-25
Supersingular isogeny graphs and endomorphism rings: reductions and solutions
Kirsten Eisentraeger, Sean Hallgren, Kristin Lauter, Travis Morrison, Christophe Petit

In this paper, we study several related computational problems for supersingular elliptic curves, their isogeny graphs, and their endomorphism rings. We prove reductions between the problem of path finding in the $\ell$-isogeny graph, computing maximal orders isomorphic to the endomorphism ring of a supersingular elliptic curve, and computing the endomorphism ring itself. We also give constructive versions of Deuring's correspondence, which associates to a maximal order in a certain...

2017/962 (PDF) Last updated: 2018-02-21
Hard and Easy Problems for Supersingular Isogeny Graphs
Christophe Petit, Kristin Lauter

We consider the endomorphism ring computation problem for supersingular elliptic curves, constructive versions of Deuring's correspondence, and the security of Charles-Goren-Lauter's cryptographic hash function. We show that constructing Deuring's correspondence is easy in one direction and equivalent to the endomorphism ring computation problem in the other direction. We also provide a collision attack for special but natural parameters of the hash function, and we prove that for general...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.