Asymptotic improvements to provable algorithms for the code equivalence problem

Huck Bennett; Drisana Bhatia; Jean-François Biasse; Medha Durisheti; Lucas LaBuff; Vincenzo Pallozzi Lavorante; Philip Waitkevich

Paper 2025/187

Asymptotic improvements to provable algorithms for the code equivalence problem

Huck Bennett, University of Colorado Boulder

Drisana Bhatia, University of California, Berkeley

Jean-François Biasse, University of South Florida

Medha Durisheti, Virginia Tech

Lucas LaBuff, University of Maryland, College Park

Vincenzo Pallozzi Lavorante, University of South Florida

Philip Waitkevich, University of South Florida

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.
Keywords: Code Equivalence Code based cryptography Code Isomorphism
Contact author(s): huckbennett @ gmail com
dbhatia1089 @ berkeley edu
biasse @ usf edu
medhad @ vt edu
lucas labuff @ gmail com
vpallozzilavorante @ gmail com
phillipwaitkevich @ usf edu
History: 2025-02-10: approved; 2025-02-08: received; See all versions
Short URL: https://ia.cr/2025/187
License: CC BY

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}
}