post-quantum cryptography engineers

Abstract: A collection of classical codes $C_1,\dots,C_m$ has product expansion if every low-weight word in the sum of their extensions to the product space can be written as a sum of words supported on few lines, each line being a codeword of the corresponding $C_i$. For $m=2$ product expansion is equivalent to robust testability of the tensor code, while for $m\ge 3$ it is strictly stronger; it is the hypothesis on the local codes behind recent constructions of good quantum LDPC codes, good quantum locally testable codes, and quantum codes with transversal non-Clifford gates. No explicit family over a fixed field was previously known to achieve constant rate, linear distance for both the code and its dual, and 3-fold product expansion at growing length. We prove that for the one-point evaluation codes $C_i$ of length $N_i=728\cdot27^{\,i-1}$ and pole order $\lfloor N_i/5\rfloor$ on the Garcia--Stichtenoth tower over $\mathbb{F}_{729}$, the triple $(C_i,C_i,C_i)$ has product expansion with a constant independent of $i$. The dual codes $C_i^\perp$ then form an explicit fixed-field family of rate tending to $109/130$ and relative distance at least $8/65$. The proof is geometric: we view the words of the sum code as arrays on the product of three copies of the $i$-th curve of the tower, where the parity checks are sections of a line bundle. An exact generation theorem describes the sum-code words supported on the grid footprint of a suitable divisor. A support-localisation argument then shows that every low-weight array lies on such a divisor, after deleting a small number of coordinates. We also give a sufficient criterion for three-fold product expansion in terms of degree and genus ratios, yielding explicit families over every non-prime finite field of order at least $512$. The principal conclusions have been formally verified in Lean 4.

Abstract: We study the cryptographic use of Shimura class group actions on superspecial principally polarized abelian varieties equipped with a CM orientation, within the context of post-quantum cryptography. Besides giving an accessible introduction to the topic, illustrated with many examples, we provide tools for representing CM orientations through higher-dimensional isogenies and for computing the Shimura class group action in the restricted effective group action model. Here, key auxiliary results are a version of Kani's lemma "with CM" and a trick that often allows to halve the ambient dimension. We also give a method for finding superspecial principally polarized abelian surfaces that are oriented by a given CM order, which is extracted from an algebraic framework for studying CM orientations using the Ibukiyama-Katsura-Oort correspondence. We also analyze obstructions to transitivity of the Shimura class group action, related to the characteristic-zero notion of CM type.

Abstract: The shortest vector problem (SVP) under the infinity norm ($\ell_\infty$-norm) is an important lattice problem with applications in lattice-based cryptography. In particular, the security analysis of the post-quantum signature standard ML-DSA highlights the importance of finding short solutions satisfying infinity-norm constraints, rather than only Euclidean norm bounds. However, most existing lattice reduction algorithms are developed for the Euclidean norm, while dedicated studies under the infinity norm remain limited. In this work, we focus on rank-two lattices in $\mathbb{R}^n$ and introduce a new notion of reduced basis under the infinity norm. Based on this definition, we propose an efficient lattice basis reduction algorithm that performs a multi-dimensional analogue of Euclidean division using a dominant coordinate of the basis vectors. Each non-terminal iteration guarantees a factor-two decrease of the maximum infinity norm of the basis vectors. We prove that the algorithm terminates and achieves a bit complexity of $O(nT^2)$, matching the asymptotic complexity order of the classical Lagrange--Gauss reduction. Moreover, the proposed algorithm saves at least $2n$ multiplications per iteration compared with the classical approach. Experiments demonstrate significant runtime improvements, especially for high-dimensional lattices. This work provides a foundation for developing lattice reduction techniques under the infinity norm.

Abstract: Deciding whether a system of multivariate quadratic equations over $\mathbb F_2$ has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let $\MQ_0(n)$ and $\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\cup_{n\geq 2} \MQ_0(n)$ is a coNP-complete language, while $\cup_{n\geq 2} \MQ_1(n)$ lies in DP. It is known that $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \[ |\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] More generally, let $Q_d$ be the space of polynomial functions $(\FF_2)^n\to\mathbb F_2$ of degree at most $d$, and let $α_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \[ α_0<α_1 \le \left(1+\frac{1}{2^n-1}\right)α_0\,, \qquad 2\le d\le n \,. \] The proof combines matroid and coding-theoretic methods. We interpret $(\FF_2)^n$ as the ground set of the evaluation matroid of $Q_d$, express $α_0$ and $α_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push $α_1-α_0$ below $α_1/2^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code $\RM(n-d-1,n)=\RM(d,n)^\perp$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.