Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic
Abstract
We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.
Related
- Embedding Linear Codes into Optimal Self-Orthogonal Codes Based on Constraint-Preserving Genetic Algorithms
- On the arithmetic Siegel--Weil formula for orthogonal Shimura varieties over a general totally real field
- Characteristic identities for orthogonal quantum matrices: examples
- First Subconstituents of Orthogonal Graphs in Even Characteristic:Automorphisms, Cliques, Cores, and Binary Triple Transitivity
- Painlevé representations for joint moments of characteristic polynomials from the orthogonal and unitary symplectic groups
BibTeX
@misc{albrecht2026algorithms,
title = {{Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic}},
author = {Martin R. Albrecht and Benjamin Benčina and Russell W. F. Lai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08664},
eprint = {2610.08664},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08664},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic
AU - Martin R. Albrecht
AU - Benjamin Benčina
AU - Russell W. F. Lai
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08664
UR - https://arxiv.org/abs/2610.08664
AB - We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.
ER -