Providing strong security margins against cryptanalytic attackers equipped with quantum computers is a major research direction fostered by the US National Institute of Standards and Technology (NIST) Post-quantum Cryptography Standardization process. Among the viable candidates, code-based asymmetric cryptosystems are one of the prominent approaches. In this work, we propose the first fully detailed quantum circuit to compute the solution to the Information Set Decoding problem, the main cryptanalytic tool against such cryptosystems. We evaluate the cryptanalytic effort with our circuit design on actual parameters from cryptosystems admitted to the final stage of the NIST standardization process and compare it with the previous conservative asymptotic estimates. We show that the actual computational effort of our solution is smaller than the one estimated via asymptotics by a factor of 24. We also perform a comparison of our results with the quantum-computational effort of breaking the AES cipher, following the guidelines of the US NIST in evaluating the security of the ciphers. To do this, we translate our design on gates of the Clifford+T gate set only, one of the most promising candidate for fault-tolerant quantum computation, and report that the parameter choices for Classic McEliece and BIKE, two candidates admitted to the final round of the NIST standardization process provide an adequate security margin with respect to our ISD solution technique.

A Complete Quantum Circuit to Solve the Information Set Decoding Problem

Perriello S.;Barenghi A.;Pelosi G.
2021-01-01

Abstract

Providing strong security margins against cryptanalytic attackers equipped with quantum computers is a major research direction fostered by the US National Institute of Standards and Technology (NIST) Post-quantum Cryptography Standardization process. Among the viable candidates, code-based asymmetric cryptosystems are one of the prominent approaches. In this work, we propose the first fully detailed quantum circuit to compute the solution to the Information Set Decoding problem, the main cryptanalytic tool against such cryptosystems. We evaluate the cryptanalytic effort with our circuit design on actual parameters from cryptosystems admitted to the final stage of the NIST standardization process and compare it with the previous conservative asymptotic estimates. We show that the actual computational effort of our solution is smaller than the one estimated via asymptotics by a factor of 24. We also perform a comparison of our results with the quantum-computational effort of breaking the AES cipher, following the guidelines of the US NIST in evaluating the security of the ciphers. To do this, we translate our design on gates of the Clifford+T gate set only, one of the most promising candidate for fault-tolerant quantum computation, and report that the parameter choices for Classic McEliece and BIKE, two candidates admitted to the final round of the NIST standardization process provide an adequate security margin with respect to our ISD solution technique.
2021
Proceedings - 2021 IEEE International Conference on Quantum Computing and Engineering, QCE 2021
978-1-6654-1691-7
post-quantum code-based cryptosystems
quantum circuit design
Quantum cryptanalysis
computer security
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

Descrizione: main article
: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 441.72 kB
Formato Adobe PDF
441.72 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/1201187
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 1
social impact