Code equivalence is a well-known concept in coding theory. Re-cently, literature saw an increased interest in this notion, due to the intro-duction 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. 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.

ON THE COMPUTATIONAL HARDNESS OF THE CODE EQUIVALENCE PROBLEM IN CRYPTOGRAPHY

Barenghi A.;
2023-01-01

Abstract

Code equivalence is a well-known concept in coding theory. Re-cently, literature saw an increased interest in this notion, due to the intro-duction 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. 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.
2023
Code equivalence
codes
cryptography
isometry
post-quantum
File in questo prodotto:
File Dimensione Formato  
Security_of_Code_Equivalence___AMC_Formatted_AIMS.pdf

accesso aperto

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 573.54 kB
Formato Adobe PDF
573.54 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1233849
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 0
social impact