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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-00863598
Contributor : Nicolas Sendrier <>
Submitted on : Thursday, September 19, 2013 - 11:29:59 AM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: Friday, December 20, 2013 - 3:08:02 PM

File

codeqapp2.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

247

Files downloads

380