The SQIparty
Abstracts
- Threshold signatures from different group actions
Giacomo Borin
Abstract: Group actions are essential tools in both discrete-logarithm-based and post-quantum cryptography, including isogeny-based (like CSI-FiSh) and code-based (like LESS) group actions. They have garnered significant interest in the cryptographic community, particularly for their ability to unlock cryptographic functionalities beyond standard encryption and signature. In this talk, we will focus on threshold signatures, providing an overview of the various schemes documented in the literature. It is important to note that not all cryptographic group actions share the same properties. Therefore, we will highlight the different advantages and limitations of various group actions, considering whether the acting group is cyclic, abelian, or neither.
- Computing two-dimensional isogenies for SQIsign
Maria Corte-Real Santos
Abstract: In this talk, we will give a gentle introduction on how to compute two-dimensional isogenies efficiently, with a focus on its application to the Round 2 SQIsign NIST submission. In particular, we will detail algorithms to compute isogenies between products of supersingular elliptic curves as a chain of 2-isogenies. To increase the efficiency of this computation, rather than working with products of elliptic curves (and more generally principally polarised abelian surfaces), we work with Kummer surfaces in the theta model. These can be seen as the analogue of the x-coordinate in dimension 2. We end the talk by applying our algorithms to the two-dimensional variants of SQIsign.
- PEGASIS: Practical Effective Class Group Action using 4-Dimensional Isogenies
Pierrick Dartois
Abstract: In this talk, we present the first practical algorithm to compute an effective group action of the class group of any imaginary quadratic order O on a set of supersingular elliptic curves primitively oriented by O. Effective means that we can act with any element of the class group directly, and are not restricted to acting by products of ideals of small norm, as for instance in CSIDH. Such restricted effective group actions often hamper cryptographic constructions, e.g. in signature or MPC protocols. Our algorithm is a refinement of the Clapoti approach by Page and Robert, and uses 4-dimensional isogenies. As such, it runs in polynomial time, does not require the computation of the structure of the class group, nor expensive lattice reductions, and our refinements allows it to be instantiated with the orientation given by the Frobenius endomorphism. This makes the algorithm practical even at security levels as high as CSIDH-4096. Our implementation in SageMath takes 1.5s to compute a group action at the CSIDH-512 security level, 21s at CSIDH-2048 level and around 2 minutes at the CSIDH-4096 level. This marks the first instantiation of an effective cryptographic group action at such high security levels. For comparison, the recent KLaPoTi approach requires around 200s at the CSIDH-512 level in SageMath and 2s in Rust.
- SQIsign: past, present and future
Luca De Feo
Abstract: In this introductory talk I will explain the central idea behind the signature scheme SQIsign and how it was originally instantiated when SQIsign was first submitted to the NIST competition. Then I will explain how SQIsign evolved after the discovery of the SIDH attacks and what changes were recently made to the 2nd round NIST submission of SQIsign. I will finish by surveying the current open problems around SQIsign.
- Algorithms for moduli space of abelian varieties with level structure
Antoine Dequay
Abstract: Let $(A, \mathcal L, \Theta_n)$ be an abelian variety of dimension $g$ together with a level $n$ theta structure over a field $k$ of characteristic different from 2. We associate $(\theta^{\Theta_\mathcal L}_i)_{(\mathbb{Z}/n\mathbb{Z})^g}$, the standard basis for theta functions, with it. The article [Fast change of level and applications to isogenies, Lubicz & Robert, 2022] focuses on level change algorithms for calculating level $dn$ theta functions, $(\theta^{\Theta_{\mathcal L^d}}_i(x))_{i \in (\mathbb{Z}/d n\mathbb{Z})^g}$, from the theta functions of level $n$, $(\theta^{\Theta_\mathcal L}_i(x))_{i \in (\mathbb{Z}/n\mathbb{Z})^g}$ (and conversely), in the case where $d$ is a positive integer prime with $n$ and the characteristic of $k$. We propose here to complete this study in the case where $d$ divides $n$. The main result of this presentation shows the existence of an algorithm for going from level $n$ to level $dn$. We deduce an algorithm to compute an isogeny $f : A \to B$ from the data of $(A, \mathcal L, \Theta_n)$ and $K \subset A[d]$, isotropic for the Weil pairing.
- A Combinatorial Perspective on Theta Structures
Max Duparc
Abstract: With each passing month, higher-dimensional abelian varieties and isogenies gain increasing relevance in cryptography. This growing importance presents a new challenge: making these concepts accessible to the broader cryptographic community by explaining both their structure and their computational aspects. To address this, we propose studying higher-dimensional isogenies through the lens of theta structures, focusing specifically on a combinatorial link between them and symplectic bases. This perspective allows us to properly explain key properties, such as the (differential) group law and isogeny computations, while minimizing the need for algebraic geometry. Furthermore, this combinatorial approach can also be used to find more efficient formulae.
- Translating ideals to isogenies
Jonathan Komada Eriksen
Abstract: In this talk, we will look at how higher-dimensional isogenies have wildly simplified ideal-to-isogeny translations as done in SQIsign. We will also compare a lot with the similar ideas that apply to PEGASIS, and highlight the differences by answering the following questions: Why can SQIsign do these translations in dimension 2, when PEGASIS works in dimension 4? Why is rerandomization necessary for both, but much more complicated in SQIsign? Finally, towards the end we will also discuss if some of the new ideas in PEGASIS can be relevant to SQIsign.
- Quaternionic multiplication and abelian fourfolds
Enric Florit
Abstract: Which quaternion algebras can act on an abelian variety defined over a finite field? The answer is known for elliptic curves and abelian surfaces, but the picture is less clear in higher dimension. The interesting cases in dimension 2 are always supersingular, and in particular QM surfaces are always geometrically split. In this talk, I will present a classification of QM abelian fourfolds, and give some principles that may lead to a study of higher dimensional varieties. In particular, we will see geometrically simple (hence non-supersingular) fourfolds with quaternionic multiplication and p-rank zero. As an application of this classification, I will show a class of geometrically simple abelian fourfolds over number fields that split modulo all primes of good reduction.
- Speeding up SQIsign verification on the ARM Cortex-M4
Décio Gazzoni Filho
Abstract: SQIsign verification performance is dominated by the cost of field arithmetic operations, whose efficient realization is aided by exploiting platform-specific features. In this talk, we describe a library that generates platform-specific code for the very popular ARM Cortex-M4 core for deeply embedded devices. It achieves field arithmetic performance that surpasses portable libraries, C code generators and even some hand-optimized assembly implementations. Of particular interest, new speed records are demonstrated for one- and two-dimensional variants of SQIsign on the Cortex-M4. Joint work with Félix Carvalho Rodrigues, Gora Adj, Isaac A. Canales-Martínez, Jorge Chávez-Saab, Julio López, Michael Scott and Francisco Rodríguez-Henríquez.
- A Montgomery-ladder for isogenies
Marc Houben
Abstract: We present a new algorithm for evaluating class group actions on oriented elliptic curves. It can be efficiently instantiated using imaginary quadratic orders of arbitrarily large class number (i.e. post-quantum security), without increasing the size of the base field. Our algorithm is fully deterministic, strictly constant-time, does not require dummy operations, and can be implemented without conditional branches.
- Exploring Kani's Research
Harun Kir
Abstract: In the isogeny-based cryptography, there has been growing interest in Kani’s research. However, it appears that many aspects of his work have yet to be fully explored within this domain. Notably, Kani dedicated a significant portion of his research and numerous papers to the study of (N,N)-isogenies. Central to his approach over the past three decades is the use of a positive definite quadratic form, so called the refined Humbert invariant. Since this invariant is a core element of my PhD thesis, I will discuss its role in the study of (N,N)-isogenies by presenting some of my results. I will also provide examples to demonstrate the power of the refined Humbert invariant theory, including a re-proof of (recent) results concerning the superspecial isogeny graph.
- Biquaternion cryptography
Péter Kutas
Abstract: Quaternion algebras play a crucial role in SQIsign through the Deuring correspondence. How does this generalize to superspecial abelian varieties? Is there hope to have a fully two-dimensional SQIsign? The talk will partially answer these questions and provide open problems for further research.
- Hidden geometry in supersingular isogeny graphs
Chloe Martindale
Abstract: We discuss both recent and ongoing work around different approaches to find patterns in supersingular isogeny graphs, with the aim of increasing our understanding of the computational hardness of variants of the isogeny problem (including those underlying SQISign). We discuss recent results exploiting the relationship to Bruhat-Tits trees and refined Humbert invariants, and present some open problems on the use of higher dimensions. This includes joint work with Laia Amoros, James Clements, and Eda Kirimli.
- SQIsign2DPush
Hiroshi Onuki
Abstract: I introduce a new variant of SQIsign that uses 2-dimensional isogenies. To efficiently compute auxiliary isogenies, we propose a new algorithm called PushRandIsog. This algorithm calculates the pushforward of an isogeny from a special curve E0 by an isogeny computed via DoublePath, a subalgorithm of SQIsignHD. Our resulting scheme reduces the required number of 2-dimensional isogeny computations compared to existing 2-dimensional variants. This is a join work with Kohei Nakagawa.
- Generalized class group actions via class field theory
Eli Orvis
Abstract: In a recent paper, Arpin, Castryk, Eriksen, Lorenzon, and Vercauteren gave free and transitive actions of generalized class groups on oriented elliptic curves with level structure. In this talk we discuss an approach to classifying these actions via class field theory. This work-in-progress has potential applications to enumerative questions about oriented elliptic curves with level structure, and gives a framework for describing these actions within a wider narrative. Joint work with Sarah Arpin and Joseph Macula.
- On prime degree twisting endomorphisms of supersingular elliptic curves
Jordi Pujolàs
Abstract: Let p and l be two distinct prime numbers such that p > 3 and l not 2, and let m = u^2 + l v^2 with u and v integers not divisible by l. Our talk has two parts. In the first one, we assume p is congruent to 3 mod 4 and -p is not a square modulo l. Under these assumptions we explain an algorithm to find all supersingular elliptic curves E over F_p that have a twisting endomorphism of degree l. Our algorithm stops when E and its quadratic twist are l-isogenous over F_p. In the second part, we assume E has a twisting endomorphism of degree l and we show that all elliptic curves l^k-isogenous to E have an endomorphism of degree m^{c_k} with c_k dividing l^k. This is joint work with J. Miret and J. Valera.
- Cryptographic Categories
Ilinca Radulescu
Abstract: We introduce a novel framework for constructing cryptographic schemes in the setting of category theory. Simply put, a category is defined as a set of objects and a set of morphisms, which obtain a list of specific properties. Since we are interested in obtaining a cryptographic category, we also introduce a list of computational axioms that the framework must satisfy. A key concept is the fingerprint, a collection of maps from the homset to a set $\mathcal{M}$, with some or all of the following properties: evaluatable, triangularizability, walkability, inidistinguishable walkability, hard and homomorphic. Using this framework, we then show how to build a hash function, a signature scheme that is analogous to SQISign, called Basic Signature, and a Chameleon-Hash function. Lastly, we instantiate our framework in the setting of elliptic curves over $\mathbb{F}_{p^2}$. We demonstrate that this instantiation obtains the computational axioms required for a cryptographic category. To instantiate the fingerprint, we offer two alternatives: the kernel and the matrix definition. The kernel definition closely emulates SQISign, while the matrix definition is akin to the level structure framework. We show the first instantiation obtains all six properties, and hence can be used to construct any of the proposed protocols. On the other hand, the second alternative may face potential limitations in obtaining the triangularazility property, and hence, be limited in its applications to the discussed protocols.
- Montgomery ladders already compute pairings
Alessandro Sferlazza
Abstract: In elliptic curve arithmetic, points are often represented via projective coordinates as an algorithmic trick to achieve division-free algorithms. Projective coordinates actually carry more algebraic information, namely related to the Tate pairing. Using a slightly adjusted version of point arithmetic in (X,Z) coordinates, called *cubical arithmetic*, we show that a Montgomery ladder gives the Weil and Tate pairing as immediate byproducts. These results arise from the theory of biextensions and cubical torsors, but yield concrete, simple algorithms for generic pairing computations, consistently reducing costs in isogeny applications with respect to the state of the art (40% in SQIsign point compression, 7% for use cases in CSIDH). [Based on joint work with G. Pope, K. Reijnders, D. Robert, B. Smith. Soon on eprint!]
- Post-quantum signatures in practice: securing IoT software updates
Benjamin Smith
Abstract: We compare a selection of post-quantum signature schemes (ML-DSA, LMS, XMMS, Falcon, and SQIsign) in a concrete application: secure software updates for RIOT OS, a free, open-source operating system for low-end IoT devices. We compare performance on several microcontroller platforms, and for a range of different typical update sizes.
- An introduction to isogeny-based cryptography
Benjamin Wesolowski
Abstract: In this introductory talk, we will present the main objects of isogeny-based cryptography and the underlying computational notions, with a view towards understanding SQIsign.
- Coding sprint
Whether you are a 10× coder, a C dummy, a Sagemath sage, or a pirate of the CSIDH, join us for the coding sprints. Don't be shy, participate at your own skill level and learn from others: dive into the SQIsign code, learn how to use Sagemath or Magma to work effectively with isogenies, or come with your own development project. Possibilities are countless and fun is guaranteed!
-
NIST Post-quantum Cryptography Q&A
All you wanted to know on NIST's selection process for post-quantum cryptographic schemes but never dared ask. Get the answers from our panel of experts who, among SIKE and SQIsign, survived fivesubmission deadlines and countless "pqc-forum" emails.
- Skillshare
What's a skillshare? The name says it all: it's a space where you share your skills. Think of it as a poster session of steroids. Want to showcase your latest development project? Want to present a research problem that had you stuck for months? Want to deliver a crashcourse on your favourite cohomology? Want to present your new Theory of Everything® or just a pet peeve? Just curious about what other people around you do?
Whether you feel like being a teacher or a learner, this session is for you. Announce your topic at the beginning of the session and get ready to present it to a small audience of interested peers. Every 15-20 minutes the audience rotates to a new presenter, so you get to learn on different topics and/or reach as wide an audience as possible.
University of Lleida, Catalonia, Spain, April 28-30, 2025.
