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

##### Abstract

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)
Category
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2022
Keywords
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
History
2022-07-28: approved
See all versions
Short URL
https://ia.cr/2022/964

CC BY

BibTeX

@misc{cryptoeprint:2022/964,
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{https://eprint.iacr.org/2022/964}},
url = {https://eprint.iacr.org/2022/964}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.