Paper 2021/1608

An Optimized Quantum Implementation of ISD on Scalable Quantum Resources

Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, José I. Latorre, and Marc Manzano


The security of code based constructions is usually assessed by Information Set Decoding (ISD) algorithms. In the quantum setting, amplitude amplification yields an asymptotic square root gain over the classical analogue. However, it is still unclear whether a real quantum circuit could yield actual improvements or suffer an enormous overhead due to its implementation. This leads to different considerations of these quantum attacks in the security analysis of code based proposals. In this work we clarify this doubt by giving the first quantum circuit design of the fully-fledged ISD procedure, an implementation in the quantum simulation library Qibo as well as precise estimates of its complexities. We show that against common belief, Prange's ISD algorithm can be implemented rather efficiently on a quantum computer, namely with only a logarithmic overhead in circuit depth compared to a classical implementation. As another major contribution, we leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs, that allow to tailor the necessary qubits to any available amount, while still providing quantum speedups. Interestingly, when constraining the width of the circuit instead of its depth we are able to overcome previous optimality results on constraint quantum search.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
ISDdecodingquantum circuitclassical-quantum trade-offscode-based
Contact author(s)
andre r esser @ gmail com
sergi ramos @ tii ae
eemanuele bellini @ gmail com
jose ignacio latorre @ tii ae
marc manzano @ google com
2021-12-09: received
Short URL
Creative Commons Attribution


      author = {Andre Esser and Sergi Ramos-Calderer and Emanuele Bellini and José I.  Latorre and Marc Manzano},
      title = {An Optimized Quantum Implementation of ISD on Scalable Quantum Resources},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1608},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.