Mathematics of Post-Quantum Cryptography

TL;DR

• What? A workshop on the Mathematics of Post-Quantum Cryptography
• When? September 7–11, 2026
• Where? Raitenhaslach, Germany (about 100 km east of Munich)

This event is the second edition of the workshop of the same name held in June 2025 at the University of Zürich.

Invited speakers

• Monika Trimoska, Eindhoven University of Technology, NL

  Graphs and cycles in curve-based collision walks show abstract

  The Parallel Collision Search algorithm by van Oorschot and Wiener remains the state-of-the-art for solving the elliptic curve discrete logarithm problem. The van Oorschot and Wiener framework has also been used to solve constrained variants of the isogeny pathfinding problem. For the generic version of the problem, however, it seemed for a long time that this approach, burdened by its huge memory requirements, can not outperform the simple yet brilliant ideas that form the Delfs–Galbraith algorithm. Recent results have reopened this question. In this talk, we go through the timeline of collision search algorithms in the isogeny setting. We explain algorithmic choices for solving the problem under some constraints before proposing a generic variant. We then play with these algorithmic tools in the multi-user setting. Here, the goal is to solve a certain number of given instances of the problem in less time than a straightforward approach where we solve each instance one by one.
• André Schrottenloher, CAPSULE, Inria Rennes, FR

  Quantum Programming for Cryptanalysts: Principles and Applications show abstract

  While asymptotic analyses of quantum attacks can often be carried out with pen and paper, estimating their concrete cost—and therefore their practical impact on modern cryptosystems—requires a much more detailed study.

  In the quantum circuit model, we translate complete algorithms into quantum circuits and optimize their resource requirements, primarily qubit count and gate count. Unlike classical computation, quantum circuits must be reversible, leading to a range of dedicated optimization techniques. Furthermore, many quantum algorithms can tolerate approximate arithmetic, enabling additional reductions in resource usage.

  In this talk, I will present the key principles behind quantum circuit programming, introduce software tools that support this process, and illustrate their use through recent work on optimizing Shor's algorithm.

• Paolo Santini, DII, Università Politecnica delle Marche, IT

  On the Hardness of Finding Permutation Automorphisms of Linear Codes show 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^(ω+h) T_Graph), with n being the code length, h the hull dimension, ω 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).

• Luca De Feo, IBM Research Zürich, CH

  How to solve the supersingular endomorphism ring problem show abstract

  I will present the state on the art on finding isogenies between supersingular elliptic curves and computing their endomorphism rings, with applications to cryptanalysis.

• Wessel van Woerden, PQShield

  A Survey of Lattice-Isomorphism-Based Cryptography show abstract

  Almost five years ago, the Lattice Isomorphism Problem (LIP) was introduced as a new hardness assumption in cryptography. Since then, many follow-up works have appeared, and in this talk I will survey these developments. We will dive into LIP variants, their cryptanalysis, basic and advanced cryptographic schemes based on LIP, and some foundational results.

Program (preliminary!)

Contributed talks

• Max Duparc: MIKE: Compact and fast NIKE from the module action show abstract

  Why use group actions when monoidal actions are simpler and sufficient ?

  This is the question we answer by introducing MIKE, (a.k.a Module Isogeny Key Exchange), a new post-quantum NIKE based on the monoidal module action which is both compact (64B) and fast (2.5ms).

  Depending on the time (and the tolerance of the audience to abstract nonsense), we shall detail more or less how to transform the highly theoretic equivalence between modules and abelian varieties into an efficient constructive tool underlying our new practical cryptographic scheme.

• Inga Paul: BSI‘s activities for the transition to Post-Quantum Cryptography show abstract

  In this talk, we look at the transition to PQC from a bureaucratic point of view. We present the official recommendations on post-quantum cryptography of Germany's Federal Office for Information Security (BSI) as well as national and international timelines and have a quick look at further BSI activities, including standardization. These activities are motivated by a study on the development of quantum computers which also motivates the talk.

• Gökberk Erdogan & Emma Munisamy: Mímir — Efficient private search from homomorphic encryption show abstract

  Private search engines allow a user to retrieve documents from a public database that are semantically similar to a text query.

  Our cryptographic protocol Mímir employs state-of-the-art homomorphic ciphertext switching techniques to realize the first stateless private search engine for highly dynamic databases.

  The security of Mímir relies on (Ring) Learning with Errors.

  Mímir is stateless as it requires no offline communication, and it achieves substantially lower online communication than prior work while improving search quality in exchange for a highly parallelizable larger server computation.

• Bharath Purtipli: Changing Your Mind Without Losing Your Identity: Fully Collision-Resistant Identity-Based Chameleon Hashing from Preimage-Sampleable Functions show abstract

  Chameleon hash functions allow collisions by design, but only for parties which hold some trapdoor information. This raises a natural question: can we grant individual, unique trapdoors to identities without compromising security? We present an identity-based chameleon hash function with full collision resistance, constructed from preimage-sampleable functions. The talk introduces the relevant security notions, explains the construction, and highlights the key ideas of its security proof.

• Giuseppe D'Alconzo: On Canonical Liftings, Group Actions, and Linkable Ring Signatures show abstract

  We introduce the notion of canonical lifting for group actions, a general framework capturing how many known group action-based signatures reduce their representation size, including the canonical forms used in the LESS signature scheme. Building on this framework, we construct Sigma protocols and a linkable ring signature (LRS) scheme. Existing LRS constructions from linear code equivalence rely on the BKP framework and the group action behind LESS, a second-round NIST PQC signature candidate; however, the latest version of LESS abandons the group action setting, and the natural LRS built on the earlier one is broken by a key-recovery attack from reusing the secret key. We show that our approach avoids this issue, and identify the properties that a canonical lifting must satisfy for the security of the LRS. Instantiating our approach with the linear code equivalence group action yields CELeReS, a linkable ring signature scheme achieving signature sizes and performance competitive with the state of the art.

• Abhinaba Mazumder: An Efficient Search-to-Decision Reductions for the Linear Code Equivalence Problem show abstract

  We present an efficient search-to-decision reduction for the Linear Code Equivalence (LCE), and thus also for the Generalised Code Equivalence (GCE) problems. We extend on the recent search-to-decision reduction for Permutation Code Equivalence (PCE) by Biasse-Micheli. We demonstrate how to recover the permutation component of the equivalence given access to a decision oracle, and subsequently show one way of recovering the diagonal and field automorphism components in deterministic polynomial time via the elegant Engel-Schneider algorithm for diagonal equivalence.

• Sina Schaeffler: SQIsign's new quaternions show abstract

  In its round 3 announcement for the additional post-quantum signature call, NIST noted that more effort for constant-time SQIsign would be desirable. Indeed, so far no implementation of SQIsign is fully constant-time, mostly because of algorithmic difficulties surrounding its central quaternion ideal and ideal-to-isogeny computations.

  For the round 3 submission, SQIsign got new algorithms for almost all operations on quaternion ideals. The goal of this change is to require smaller integers and ease future efforts towards a constant-time implementation of SQIsign.

  These improvements are achieved by developing specialized methods for the ideals occurring in the scheme, most of which are left ideals of a special order O0, where the previous implementation relied on more generic methods. This specialization extends ePrint 2026/185.

  Depending on time available, the talk will focus more on the goals and impacts of this change, especially for efficiency and secure implementations, or also incorporate an explanation of the fundamental ideas of the new methods.

• Ryann Cartor: Quadratic Modelings of Syndrome Decoding show abstract

  The Syndrome Decoding Problem (SDP) plays a fundamental role in Code Based Cryptography. This talk will present reductions of the bounded-weight and exact-weight Syndrome Decoding Problem to a system of quadratic equations. Over 𝔽₂, we improve on a previous work and study the degree of regularity of the modeling of the exact weight SDP. Additionally, we introduce a novel technique that transforms SDP instances over 𝔽_q into systems of polynomial equations and thoroughly investigate the dimension of their varieties. Experimental results are provided to evaluate the complexity of solving SDP instances using our models through Groebner bases techniques. This is joint work with Alessio Caminata, Alessio Meneghetti, Rocco Mora, and Alex Pellegrini.

• Michael Schaller: An Attack on High Rate McEliece Cryptosystems Using Generalized Reed Solomon Codes with Weight 2 Mask show abstract

  Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix M with larger row and column weight.

  In many of them, the secret key is still a GRS code.

  Two proposals using M with row and column weight between 1 and 1 + R (where R is the rate of the code) have been broken previously. The case of weight 2 and higher has been left open open.

  We provide distinguishers for the public codes appearing in the cryptosystems in the high rate regime.

  In addition, we give a framework to turn a good enough distinguisher into a key recovery attack.

  In the case where the matrix M has row and column weight 2, we can successfully attack the scheme in the high rate regime using a cube code distinguisher.

  This is joint work with Julia Lieb and Abhinaba Mazumder.

Organizers: Violetta Weger and Lorenz Panny.

We gratefully acknowledge financial support by the Technical University of Munich (TUM) and by the German Research Foundation (DFG) under project number 586983745.