Welcome to the resource topic for 2025/187
Title:
Asymptotic improvements to provable algorithms for the code equivalence problem
Authors: Huck Bennett, Drisana Bhatia, Jean-François Biasse, Medha Durisheti, Lucas LaBuff, Vincenzo Pallozzi Lavorante, Philip Waitkevich
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:
- A deterministic algorithm running in 2^{n + o(n+q)} time for LCE.
- A randomized algorithm running in 2^{n/2 + o(n+q)} time for LCE and PCE.
- 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.
ePrint: https://eprint.iacr.org/2025/187
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .