Uniform samplers for linear codes with fixed hull dimensions
Uniform Sampling of Linear Codes with Prescribed Hull Dimension
Information Theory
Summary
The paper addresses how to randomly generate linear error-correcting codes that have a specific type of structure called the hull, which is important for certain inner products used in coding theory. The authors provide exact methods to sample these codes uniformly, meaning every code with the desired hull property has an equal chance of being chosen. Their approach works efficiently over various kinds of finite fields and inner product types. This is the first such method available in most cases except one special case already studied.
What this means in practice
- •For cryptographic protocol developers: Generate linear codes with exact hull dimensions to construct secure codes for cryptographic schemes needing precise hull properties.
- •For quantum error correction engineers: Create linear codes satisfying symplectic hull dimension constraints to design quantum error-correcting codes with guaranteed structural features.
Authors
Keita Ishizuka
Abstract
We give exactly uniform samplers for linear codes with prescribed hull dimension, for the Euclidean, Hermitian, and symplectic inner products and over finite fields of every characteristic. Except for the Euclidean form over fields of odd characteristic, these are the first uniform samplers for arbitrary prescribed hull dimension. Each sample costs an expected $O(k^2 N + k \log q)$ field operations for codes of dimension $k$ in a space of dimension $N$ over $\mathbb{F}_q$ or $\mathbb{F}_{q^2}$.