Quantum information set decoding algorithms

DOI10.1007/978-3-319-59879-6_5zbMATH Open1429.94060arXiv1703.00263OpenAlexW2591819627MaRDI QIDQ1673589FDOQ1673589

Authors: Ghazal Kachigar, Jean-Pierre Tillich 

Publication date: 12 September 2018

Abstract: The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem by Bernstein, Jeffery, Lange and Meurer. This results in improving the worst-case complexity of $2^{0.06035n}$ of Bernstein's algorithm to $2^{0.05869n}$ with the best algorithm presented here (where $n$ is the codelength).

Full work available at URL: https://arxiv.org/abs/1703.00263

Recommendations

• Improved quantum information set decoding
• Information-set decoding for linear codes over \(\mathbb F_q\)
• Improved information set decoding for code-based cryptosystems with constrained memory
• Hybrid decoding -- classical-quantum trade-offs for information set decoding
• Analysis of information set decoding for a sub-linear error weight

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35)

Cited In (28)

• Syndrome Decoding Estimator
• Lattice Sieving via Quantum Random Walks
• Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
• Quantum key search for ternary LWE
• Analysis of information set decoding for a sub-linear error weight
• Hybrid decoding -- classical-quantum trade-offs for information set decoding
• Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
• Improved classical and quantum algorithms for subset-sum
• A new approach based on quadratic forms to attack the McEliece cryptosystem
• Information-set decoding for linear codes over \(\mathbb F_q\)
• Improved quantum information set decoding
• Smaller decoding exponents: ball-collision decoding
• Finding many collisions via reusable quantum walks. Application to lattice sieving
• Structural properties of self-dual monomial codes with application to code-based cryptography
• Improved quantum algorithms for the k-XOR problem
• A secure and efficient code-based signature scheme
• McEliece needs a break -- solving McEliece-1284 and quasi-cyclic-2918 with modern ISD
• Decoding quantum information via the Petz recovery map
• Improved information set decoding for code-based cryptosystems with constrained memory
• Wave Parameter Selection
• Solving the learning parity with noise problem using quantum algorithms
• Interleaved Prange: a new generic decoder for interleaved codes
• A post-quantum hybrid encryption based on QC-LDPC codes in the multi-user setting
• Cryptanalysis of LEDAcrypt
• DAGS: key encapsulation using dyadic GS codes
• Memory-efficient quantum information set decoding algorithm
• On the dimension and structure of the square of the dual of a Goppa code
• On the (in)security of optimized Stern-like signature schemes

This page was built for publication: Quantum information set decoding algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1673589)