Quantum information set decoding algorithms

DOI10.1007/978-3-319-59879-6_5MaRDI QIDQ1673589zbMATH OpenOpenAlexFDO

Authors Ghazal Kachigar, Jean-Pierre Tillich

Publication date 12 September 2018

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

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35)

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).

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

Cited in

(28)

• On the (in)security of optimized Stern-like signature schemes
• Syndrome Decoding Estimator
• Classical and quantum algorithms for generic syndrome decoding problems and applications to the Lee metric
• Quantum key search for ternary LWE
• Lattice Sieving via Quantum Random Walks
• 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
• Improved quantum information set decoding
• A new approach based on quadratic forms to attack the McEliece cryptosystem
• Information-set decoding for linear codes over \(\mathbb F_q\)
• 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
• A secure and efficient code-based signature scheme
• Improved quantum algorithms for the k-XOR problem
• 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
• A post-quantum hybrid encryption based on QC-LDPC codes in the multi-user setting
• Interleaved Prange: a new generic decoder for interleaved codes
• Cryptanalysis of LEDAcrypt
• DAGS: key encapsulation using dyadic GS codes
• On the dimension and structure of the square of the dual of a Goppa code
• Memory-efficient quantum information set decoding algorithm

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)