The Hardness of Code Equivalence over $\mathbf{F}_q$ and its Application to Code-based Cryptography

Nicolas Sendrier (1) , Dimitrios E. Simos (2)

1 SECRET - Security, Cryptology and Transmissions
2 sba-research

The code equivalence problem is to decide whether two linear codes over F_q are equivalent, that is identical up to a linear isometry of the Hamming space. In this paper, we review the hardness of code equivalence over F_q due to some recent negative results and argue on the possible implications in code-based cryptography. In particular, we present an improved version of the three-pass identification scheme of Girault and discuss on a connection between code equivalence and the hidden subgroup problem.

Mots clés: code-based cryptosystems; quasi-dyadic codes; efficient algorithms

Domaines: Cryptographie et sécurité [cs.CR]

Nicolas Sendrier, Dimitrios E. Simos. The Hardness of Code Equivalence over $\mathbf{F}_q$ and its Application to Code-based Cryptography. Post-Quantum Cryptography - PQCrypto 2013, Jun 2013, Limoges, France. pp.203-216, ⟨10.1007/978-3-642-38616-9⟩. ⟨hal-00863598⟩