Algorithms sample self-orthogonal codes for code-based cryptography
Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic
Information Theory
Summary
Cryptographic systems often rely on special types of codes called self-orthogonal or self-dual codes, but generating these codes randomly and fairly has been challenging. The authors revisit and improve an existing algorithm to produce such codes over certain mathematical fields, enabling new cryptographic schemes. They also study a stricter form of orthogonality involving all symmetries of these codes, providing algorithms to handle that condition. While their method reduces code rate somewhat, it is important for security in certain cryptographic problems.
What this means in practice
- •For cryptographic engineers: Generate uniformly random self-orthogonal and self-dual codes for secure code-based cryptosystems relying on Permutation Code Equivalence hardness.
- •For security protocol developers: Create cryptographic protocols that use total orthogonality codes to improve security assumptions involving symmetries over extension fields.
Authors
Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai
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.