Abstracts

Abstract: One method for solving a polynomial system is computing a Groebner basis. Therefore, it is important to be able to estimate the complexity of computing the Groebner basis of a given polynomial system. This can be done by computing or estimating related invariants, such as the solving degree and the last fall degree of the system.

In this talk, we will introduce and compare these invariants and present some examples of estimates related to multivariate cryptography.

Abstract: Solving polynomial systems of equations is one of the fundamental problems in algebraic cryptanalysis. The problem lies at the core of multivariate cryptography and also features in the analysis of other post-quantum and symmetric schemes.
This talk will focus on the polynomial system solving problem over large fields in the determined case (where there is an equal number of equations and variables). We will start by revisiting the current best methods, which rely on Gröbner basis computation and FGLM-like algorithms, before exploring a new approach that can achieve speed-ups for some parameter regimes.
This is an ongoing work with Irene di Muzio and Enrico Piccione.

Abstract: The analysis of systems of polynomial equations arising in the study of post-quantum multivariate signatures, such as UOV and its variants, is only possible under various regularity assumptions. A first example is that the sequence of polynomials in a UOV public key must be a regular sequence, otherwise the complexity analysis of the direct forgery attack fails. More involved assumptions must be made for more sophisticated attacks, for instance the semi-regularity of the sequences of polynomials arising in the Intersection attack of Beullens, the absence of false positives in the Kipnis-Shamir attack, the precise Hilbert series obtained in the different modelings of the MinRank problem, etc.
We introduce tools that intend to at least partially solve the issue of relying on heuristics that can be hard to verify experimentally for cryptographic parameters, by proving that these regularity properties hold for UOV keys belonging to Zariski open subsets of quadratic polynomial sequences.
In some cases, we are able to prove that these Zariski-open sets are non-empty in any field of characteristic not two, and in all cases these sets are non-empty if the characteristic is sufficiently large. For various small instances of UOV and its variants, we have performed experiments in small fields, which prove the non-emptiness of these sets and thus the genericity of our results.
Finally, we apply these results to formally prove heuristics used in the analysis of several attacks against UOV and its variants.
Joint work with S. Abelard and M. Safey el Din.

Abstract: The eXtended Linearization (XL) algorithm is an algebraic method for solving systems of polynomials in multiple variables. It achieves this by finding the kernel of the Macaulay matrix for some degree d, which must be high enough that the Macaulay matrix gives an overdetermined linear system. However, this degree is a rather coarse parameter. This leads to cases where XL uses excessively large systems, because the system for one degree lower is only slightly underdetermined. To reduce this coarseness, we propose a generalization of XL that uses submatrices of the Macaulay matrix. This allows for intermediate options between the integer values of the degree.

Abstract: The goal of this talk is to present three bilinear systems arising from the algebraic cryptanalysis of code-based constructions that I studied this year, namely the McEliece encryption scheme and two MPC-in-the-Head signature schemes. This will also be an opportunity to review the current state of knowledge on solving overdetermined bilinear systems, which remains much more limited than in the underdetermined case.

References:
https://eprint.iacr.org/2026/1232 https://eprint.iacr.org/2026/916

Abstract: In algebraic cryptanalysis we usually want to find a single vector that satisfies a polynomial system. But what if the solution is an entire subspace? For example, in UOV the secret key is a literal subspace. MinRank also has a secret subspace, if we know the kernel space of the secret low-rank codeword then we can efficiently find this codeword. One way to model such spaces is through parametrizing its basis vectors as is done in the Kipnis-Shamir model for MinRank and the Reconciliation attack for UOV. Alternatively, we can parametrize its minors as in the Support-Minors model, or work in the exterior algebra as in the wedge product attack. In this talk, we will explore how these models are related through the Plücker embedding. We will build a dictionary by showing how relations between subspaces imply relations between minors and vice-versa.

Abstract: Given a polynomial system of m polynomials and n variables over a finite field Fp, finding its solutions is a NP-complete problem. Commonly used methods to solve these systems are algorithms computing Gr¨obner basis (F4, F5) or based on linear algebra (XL). In this work, we focus on the M Q (Multivariate Quadratic) problem, which means that we consider polynomials of degree 2. In particular, we are interested in the case where the polynomial system is defined over F2. In this case, exhaustive search becomes a viable way to solve a polynomial system (FES). Another approach consists in specifying some of the variable and try solving the resulting systems via algebraic approach. In particular, this is the idea behind the Crossbred algorithm [JV17].

Crossbred is one of the most efficient algorithm in practice, with implemen- tations breaking records on the Fukuoka MQ challenge1. Previous work on this algorithm suggests there is room for improvement on its running time. In a first step, called pre-processing, the algorithm generates polynomials with certain properties. These polynomials are added to the initial system, which is eventu- ally solved after specialisation of certain variables. However, it was shown that the number of polynomials generated most of the case is far greater that the mininimal number of necessary polynomials. With that in mind, we propose an analysis on the minimal number of polynomials needed and, as a consequence, an improvement of the pre-processing of the Crossbred algorithm. Moreover, we propose our own complexity of the pre-processing as we noted a common mistake in previous works in the complexity of the algorithm. I will also present our complexity for the pre-proccesing and we use this result to analyse the security of MQOM.

Abstract: Come on, you've all seen https://ia.cr/2026/1486, what do you think I'm going to talk about?

Abstract: In dimension 1, isogeny graphs are beautiful, simple, and Ramanujan. This ensures their expansion properties are excellent, which initiated early isogeny-based cryptography. When we move up in dimension, however, things fall apart. The beauty and simplicity are lost, and even though the expansion properties are not bad, they are no longer optimal. One might wonder "are we even looking at the correct generalization?" What is the "right" definition for the isogeny graph whose properties we care about for higher-dimensional isogeny-based cryptography?

To answer this question, we need a solid understanding of the analogue of elliptic curves in dimension 2: abelian surfaces. We give a gentle introduction to abelian surfaces, their automorphisms, and their isogenies. This enables us to define the "ordinary" badly-behaving isogeny graphs, but also superspecial digraphs! We conjecture that these superspecial digraphs are the relevant isogeny graphs for isogeny-based cryptography, and study their expansion properties. This finally answers some questions, but opens the door to many new mysteries, yet unsolved...

Abstract: Since the introduction of the SIDH attacks, isogeny-based cryptography does not only study elliptic curves but uses higher dimensional abelian varieties in many different ways. Once one moves up to higher dimensions many relatively simple concepts become much more convoluted, most prominently one has to work with principal polarizations and polarized isogenies which introduce many technical difficulties. However, just as in dimension 1, one can study endomorphism rings of superspecial abelian varieties and all geometric notions have an algebraic counterpart. In my talk, I will explore this algebraic world and study surfaces with extra structure and their algebraic properties. This leads to many open problems that are purely algebraic in nature and require no knowledge about principal polarizations.

Abstract: We describe a Las Vegas algorithm for the principal ideal problem in matrix rings M_g(O) for g >= 2, over maximal orders O in the rational quaternion algebra B_p,inf ramified at infinity and a prime number p. Under plausible heuristic assumptions, the method has expected polynomial runtime. An implementation in SageMath shows that it runs very efficiently in practice, with compact output. Our main auxiliary result is a method for finding endomorphisms of superspecial abelian varieties (i.e., powers of supersingular elliptic curves) with a prescribed kernel.

Abstract: The security of several cryptography protocol reduces to the computation of an automorphism of a large projective space mapping some public projective variety X to a reference variety X_0. For certain choices of X_0, computing such an automorphism reduces to computing an isomorphism of representations of Lie algebras, which amounts to solving a system of linear equations. We discuss the method in detail, and the hypotheses it requires.

Abstract: The security of many isogeny-based cryptographic constructions relies on the hardness of finding the endomorphism ring of a random supersingular elliptic curve over F_{p^2} The state-of-the-art algorithms to solve the EndRing problem are based on the Delfs-Galbraith algorithm: given a random input curve, randomly walk in the supersingular isogeny graph until you hit a curve over 𝔽ₚ; this walk reduces EndRing to a vectorization problem on the 𝔽ₚ-subgraph, which is easier to solve. In this talk, we see that we can explore the isogeny graph more efficiently via SIDH isogeny ladders and expand the choice of destination subgraphs via orientations. As a result, we get asymptotic as well as concrete improvements: via these optimizations we realized a memory-effective GPU implementation, solving random instances of the EndRing problem for primes p ≲ 2^100 within a day.

Abstract: Finding a nontrivial endomorphism of a given supersingular elliptic curve is a hardness assumption of isogeny-based cryptography. We prove the reduction from it to the problem of finding a splitting of a given principally polarized abelian surface. By using this new reduction, we also prove the heuristic equivalence of the splitting problem with a degree restriction and the endomorphism ring problem in dimension two. This is joint work with Péter Kutas.

Abstract: Many hard problems underlying code- and lattice-based cryptography can be cast as isomorphism problems: given two objects, determine whether a hidden group element maps one to the other. In this talk, we present a general framework for attacking such problems using tools from invariant theory and algebraic geometry. The central idea is to study the action of the relevant group on the object space and construct invariant functions that are unchanged by the "easy" part of the hidden transformation, isolating the "hard" part as a root of an explicit system of polynomial equations. We illustrate this framework using the Linear Code Equivalence (LCE) problem, where the hidden transformation is a monomial matrix decomposable into a diagonal part and a permutation part. Using Plücker coordinates and invariant rational functions on the Grassmannian, we exploit algebraically independent invariants under diagonal scaling, yielding polynomial equations with the hidden permutation as a root. We discuss how this construction generalizes beyond LCE to other isomorphism problems, and outline the current limitations and open questions in turning such invariant-theoretic constructions into practical cryptanalytic tools.

Abstract: Modern cryptography relies on digital signature schemes built from a variety of computational assumptions, ranging from lattices and error-correcting codes to multivariate polynomial systems. While these constructions often appear highly specialized, the MPC-in-the-Head paradigm provides a remarkably generic framework that can transform virtually any hard computational problem into a practical signature scheme.

This talk focuses on the latest MPC-in-the-Head frameworks that have made this paradigm practical for real-world post-quantum signatures. We will explain the key ideas behind these modern constructions, how they efficiently instantiate the MPC-in-the-Head approach, and how successive generations of protocols have significantly improved performance while preserving the generic nature of the framework.

Through representative examples, we will show how these frameworks enable the construction of competitive signature schemes from fundamentally different hardness assumptions, including code-based, multivariate, and symmetric cryptography. The goal of this presentation is to provide an accessible overview of the modern MPC-in-the-Head landscape and to illustrate why it has become one of the most versatile approaches to designing post-quantum digital signatures.

Abstract: We strengthen a recent generic construction by Derler, Krenn, Samelin and Slamanig to instantiate the first isogeny-based fully collision-resistant chameleon hash function (building on the CGL hash function), thus also enabling other advanced primitives such as isogeny-based sanitizable signatures, at the cost of large randomness. By weakening the assumption on the underlying commitment scheme in the construction, we show that our chameleon hash function also does not require a trusted setup, in contrast to the regular CGL hash function. Joint work (in progress) with Thomas den Hollander and Leon Weingarten. .

Abstract: The Elliptic Curve Digital Signature Algorithm (ECDSA) is one of the most widely deployed digital signature schemes and has consequently been the subject of extensive cryptanalytic and side-channel research. In particular, lattice-based attacks exploiting partial nonce leakage have been widely studied due to their practical relevance, with new methods aiming to improve the computation time, success rate, and amount of sampled information needed to complete these attacks. We first consider an existing lattice attack method which involves guessing bits of nonces in order to improve the success rate of the attack. We propose a potential optimization for this method which uses information from one nonce guess to speed up computations associated with the next nonce guess. We then give a framework for combining bit-guessing methods with Dimensions for Free (D4F) and derive an explicit formula for the increase in the optimistic expected number of dimensions for free after guessing c bits. We also use numerical methods to find the increase in the pessimistic expected number of dimensions for free in various settings. In doing so, we formally validate the expectation that bit-guessing methods should give more dimensions for free, thus suggesting that the two methods may interact in a non-trivial way and potentially yield synergistic benefits

Abstract: I'll present some results on the multiplicative structure of dual Goppa codes, in particular their decomposition into direct sums of geometric progressions with the same common ratio. I'll explain how this allows to simplify or reinterpret some results related to the cryptanalysis of the McEliece system, such as my syzygy distinguisher, or also a recent key-recovery algorithm obtained jointly with P. Briaud, A. Lemoine, and J.-P. Tillich, whose asymptotic complexity heuristically seems to be subexponential in the error correcting capability of the underlying Goppa code.

Abstract: The Rank Syndrome Decoding problem is the computational foundation of several post-quantum cryptosystems, yet our understanding of its complexity remains surprisingly limited. In contrast to the Hamming metric, where decades of research have produced a rich collection of combinatorial and algebraic decoding techniques, rank-metric decoding is still dominated by two approaches: support enumeration and reductions to MinRank.

In this talk I will revisit these approaches, explain where they succeed and where they fall short. I will present some recent work introducing a new hybrid approach and discuss a new perspective via associated Hamming-metric codes. This viewpoint raises a number of intriguing open questions: Why do classical information-set decoding improvements fail to transfer? Can dual attacks be generalized to the rank metric? And where should we search for the next breakthrough in rank-metric decoding?

Abstract: This talk is based on a joint (and upcoming) work with Michele Battagliola, Giuseppe D'Alconzo, Laura Mattiuz and Federica Zanetti. The talk focuses on the hardness of finding permutation automorphisms of liner codes defined over finite fields. Let AUT-gen refer to the problem of finding generators for the automrphism group (in the talk, we briefly mention also related problems, such as that of finding one non trivial automorphism). We show that AUT-gen is, unsurprisingly, related to the Permutation Equivalence Problem (PEP). Since PEP is known to be easy for codes having a small hull dimension, one expects that for automorphism problems analogous considerations hold. We show that this is indeed true. In particular, we prove that any solver for AUT-gen can (in worst case quasi-polynomial time) be turned into a solver for PEP. Moreover, we adapt a reduction from PEP to the Graph Isomorphism Problem (GIP) and make it work also for automorphisms. By doing this, we get a solver for AUT-gen which runs in worst case time $O(n^{\omega+h} T_{Graph})$, with $n$ being the code length, $h$ the hull dimension, $\omega$ the exponent for matrix inversion and $T_{Graph} the (worst case) cost for solving the resulting graph automorphism problem. For hull dimension $h = O(\log(n) )$, this implies AUT-gen can be solved in worst-case quasi-polynomial time. A proof-of-concept implementation of our algorithms show that they are much faster than Sagemath and Magma implementations for the state-of-the-art solvers (Leon's and Feulner's algorithms).

Abstract: In this talk we introduce a new model, based on elementary symmetric polynomials, that can be used to solve the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. We provide an estimate of its computational complexity by showing bounds on the degree of regularity and on the solving degree of the ideal associated with the model. The estimate turns out to be lower than the one provided for previous polynomial models. The model is later slightly modified, to provide a variant whose complexity depends directly on the specific instance of the SDP and is lower than the previous. We conclude with some results on a linear algebra problem arising from the complexity analysis. Based on joint work with Elisa Gorla.