Paper 2022/967

On the Computational Hardness of the Code Equivalence Problem in Cryptography

Alessandro Barenghi, Politecnico di Milano
Jean-Francois Biasse, University of South Florida
Edoardo Persichetti, Florida Atlantic University
Paolo Santini, Universita Politecnica delle Marche

Code equivalence is a well-known concept in coding theory. Recently, literature saw an increased interest in this notion, due to the introduction of protocols based on the hardness of finding the equivalence between two linear codes. In this paper, we analyze the security of code equivalence, with a special focus on the hardest instances, in the interest of cryptographic usage. Our work stems from a thorough review of existing literature, identifies the various types of solvers for the problem, and provides a precise complexity analysis, where previously absent. Furthermore, we are able to improve on the state of the art, providing more efficient algorithm variations, for which we include numerical simulation data. Our results include also a dedicated method for solving code equivalence with a quantum algorithm, as well as a refinement of quantum Information-Set Decoding (ISD) algorithms. In the end, the goal of this paper is to provide a complete, single point of access, which can be used as a tool for designing schemes that rely on the code equivalence problem.

Note: This is the extended version of the paper published in AMC.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Advanced in Mathematics of Communication
Code Equivalence Linear Codes Signature Schemes
Contact author(s)
alessandro barenghi @ polimi it
biasse @ usf edu
epersichetti @ fau edu
p santini @ staff univpm it
2022-07-28: approved
2022-07-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alessandro Barenghi and Jean-Francois Biasse and Edoardo Persichetti and Paolo Santini},
      title = {On the Computational Hardness of the Code Equivalence Problem in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2022/967},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.