Paper 2024/1272
An Improved Algorithm for Code Equivalence
Abstract
We study the linear code equivalence problem (LEP) for linear $[n,k]$codes over finite fields $\mathbb{F}_q$. Recently, Chou, Persichetti and Santini gave an elegant heuristic algorithm that solves LEP over large finite fields (with $q = \Omega(n)$) in time $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$, where $\operatorname{H}(\cdot)$ denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size $q = \mathcal{O}(1)$, its runtime increases by an exponential factor $2^{\Theta(n)}$. We present an improved and provably correct version of their algorithm, which achieves the desired runtime of $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$ for all finite fields of size $q \geq 7$. For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 Linear Code Equivalence ProblemCanonical Form Functions
 Contact author(s)
 julian nowakowski @ rub de
 History
 20240812: approved
 20240812: received
 See all versions
 Short URL
 https://ia.cr/2024/1272
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1272, author = {Julian Nowakowski}, title = {An Improved Algorithm for Code Equivalence}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1272}, year = {2024}, url = {https://eprint.iacr.org/2024/1272} }