Cryptology ePrint Archive: Report 2021/1608

An Optimized Quantum Implementation of ISD on Scalable Quantum Resources

Andre Esser and Sergi Ramos-Calderer and Emanuele Bellini and José I. 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, 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.

Category / Keywords: public-key cryptography / ISD, decoding, quantum circuit, classical-quantum trade-offs, code-based

Date: received 9 Dec 2021

Contact author: andre r esser at gmail com, sergi ramos at tii ae, eemanuele bellini at gmail com, jose ignacio latorre at tii ae, marc manzano at google com

Available format(s): PDF | BibTeX Citation

Version: 20211209:193112 (All versions of this report)

Short URL: ia.cr/2021/1608


[ Cryptology ePrint archive ]