Paper 2022/964

Hybrid Decoding -- Classical-Quantum Trade-Offs for Information Set Decoding

Andre Esser, Technology Innovation Institute
Sergi Ramos-Calderer, Technology Innovation Institute, University of Barcelona
Emanuele Bellini, Technology Innovation Institute
José Ignacio Latorre, Technology Innovation Institute, University of Barcelona, National University of Singapore
Marc Manzano, SandboxAQ

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, already the most basic ISD algorithm by Prange suffers enormous width requirements caused by the quadratic description length of the underlying problem. Even if polynomial, this need for qubits is one of the biggest challenges considering the application of real quantum circuits in the near- to mid-term. In this work we overcome this issue by presenting the first hybrid ISD algorithms that allow to tailor the required qubits to any available amount while still providing quantum speedups of the form $T^\delta$, $0.5<\delta <1$, where $T$ is the running time of the purely classical procedure. Interestingly, when constraining the width of the circuit instead of its depth we are able to overcome previous optimality results on constraint quantum search. Further we give an implementation of the fully-fledged quantum ISD procedure and the classical co-processor using the quantum simulation library Qibo and SageMath.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2022
decoding ISD width reduction hybrid algorithms code-based cryptography
Contact author(s)
andre esser @ tii ae
Sergi Ramos @ tii ae
emanuele bellini @ tii ae
jose ignacio latorre @ tii ae
marc @ sandboxaq com
2022-07-28: approved
2022-07-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andre Esser and Sergi Ramos-Calderer and Emanuele Bellini and José Ignacio Latorre and Marc Manzano},
      title = {Hybrid Decoding -- Classical-Quantum Trade-Offs for Information Set Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2022/964},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.