Welcome to the resource topic for 2022/964
Title:
Hybrid Decoding – Classical-Quantum Trade-Offs for Information Set Decoding
Authors: Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, José Ignacio Latorre, and Marc Manzano
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.
ePrint: https://eprint.iacr.org/2022/964
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .