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

(36)

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

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)