Paper 2025/187 Original: eprint.iacr.org/2025/187 ↗
Asymptotic improvements to provable algorithms for the code equivalence problem
Abstract
We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length $n$ and dimension $k$ over any finite field $\mathbb{F}_q$, we show: 1) A deterministic algorithm running in $2^{n + o(n+q)}$ time for LCE. 2) A randomized algorithm running in $2^{n/2 + o(n+q)}$ time for LCE and PCE. 3) A quantum algorithm running in $2^{n/3 + o(n+q)}$ time for LCE and PCE. The first algorithm complements the deterministic roughly $2^n$-time algorithm of Babai (SODA 2011) for PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times, but only for code equivalence on \emph{random} codes and only over fields of order $q \geq 7$.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2025-02-08: last updated
- 2025-02-08: published
- Short URL
- https://ia.cr/2025/187
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/187,
author = {Huck Bennett and Drisana Bhatia and Jean-François Biasse and Medha Durisheti and Lucas LaBuff and Vincenzo Pallozzi Lavorante and Philip Waitkevich},
title = {Asymptotic improvements to provable algorithms for the code equivalence problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/187},
year = {2025},
url = {https://eprint.iacr.org/2025/187}
}