Paper 2026/995

On Arithmetic Invariants for Permutation Equivalence

Abstract

We give an efficiently computable invariant we call the square class invariant for the (Signed) Permutation Code Equivalence ((S)PCE) problem, that was previously not recognised in coding theory, which arises from the arithmetic of quadratic forms over finite fields. Our invariant naturally yields a distinguisher for the decision version of (S)PCE as defined at Eurocrypt 2025 by Albrecht, Benčina and Lai [ABL25], breaking the hardness assumption that underpins the security of their updatable public-key encryption scheme. We extend a 2023 result by Bruin, Ducas and Gibbons by fully classifying the genera of $q$-ary lattices, showing the genus is completely determined by the hull dimension and our square class invariant of the underlying linear code, and that none of these genera split non-trivially into spinor genera (as soon as the lattice dimension is at least 5), implying the genus of a $q$-ary lattice encodes all known efficiently computable coding-theoretic invariants for (S)PCE and vice versa. Thus our distinguisher can also be seen as comparing the genera of Construction A lattices of the (S)PCE instance in the spirit of the Lattice Isomorphism Problem. We give a complete description of the genus distribution of uniform $q$-ary lattices. This motivates the definition of a genus of a linear code as the genus of the Construction A lattice of any of its generator matrices. We adapt the sampling algorithm from [ABL25] to sample from a single genus uniformly at random and can thus restrict their hardness assumption for (S)PCE to a single genus. Restricting PCE to one genus and using our sampling algorithm is then used with a slight modification to the security proof to mend the scheme from [ABL25].