Research Article
A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems
@INPROCEEDINGS{10.1007/978-3-030-90022-9_25, author={Simone Perriello and Alessandro Barenghi and Gerardo Pelosi}, title={A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems}, proceedings={Security and Privacy in Communication Networks. 17th EAI International Conference, SecureComm 2021, Virtual Event, September 6--9, 2021, Proceedings, Part II}, proceedings_a={SECURECOMM PART 2}, year={2021}, month={11}, keywords={Post-quantum cryptography Code based cryptography Information set decoding}, doi={10.1007/978-3-030-90022-9_25} }- Simone Perriello
Alessandro Barenghi
Gerardo Pelosi
Year: 2021
A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems
SECURECOMM PART 2
Springer
DOI: 10.1007/978-3-030-90022-9_25
Abstract
The significant interest in cryptographic primitives providing sound security margins when facing attacks with quantum computers is witnessed by the ongoing USA National Institute of Standards and Technology Post-quantum Cryptography Standardization process. Sound and precise evaluation of the amount of computation required to break such cryptographic primitives by means of quantum computers is required to be able to choose the cryptosystem parameters.
We present a full description of a quantum circuit to accelerate the computation of the solution of the Information Set Decoding problem , which is currently the best known non-structural attack against code-based cryptosystems. We validate our design running it on small instances of error correction codes, which allowed a complete validation on the AtoS QLM quantum computer simulator. We detail the circuit accelerating the exponential complexity search phase in the Lee and Brickell variant of the ISD solver, and provide its computational complexity for cryptographically relevant parameters taken from the third round candidates in the USA post-quantum standardization process.
