Improved quantum information set decoding

DOI10.1007/978-3-319-79063-3_24MaRDI QIDQ1644798zbMATH OpenOpenAlexFDO

Authors Elena Kirshanova

Publication date 22 June 2018

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

zbMATH Keywords

information set decodingnear neighbourquantum walk

Mathematics Subject Classification ID

Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: In this paper we present quantum information set decoding (ISD) algorithms for binary linear codes. First, we give an alternative view on the quantum walk based algorithms proposed by Kachigar and Tillich (PQCrypto'17). It is more general and allows to consider any ISD algorithm that has certain properties. The algorithms of May-Meuer-Thomae and Becker-Jeux-May-Meuer satisfy these properties. Second, we translate May-Ozerov Near Neighbour technique (Eurocrypt'15) to an `update-and-query' language more suitable for the quantum walk framework. First, this re-interpretation makes possible to analyse a broader class of algorithms and, second, allows us to combine Near Neighbour search with the quantum walk framework and use both techniques to give a quantum version of Dumer's ISD with Near Neighbour.

Recommendations

• Quantum information set decoding algorithms
• Hybrid decoding -- classical-quantum trade-offs for information set decoding
• Quantum Rate-Distortion Coding of Relevant Information
• Enhanced Feedback Iterative Decoding of Sparse Quantum Codes
• Decoding quantum information via the Petz recovery map
• Efficient decoding of random errors for quantum expander codes
• Source coding with quantum side information at several decoders
• scientific article; zbMATH DE number 5582982
• Quantum–enhanced information processing

Cited in

(10)

• Quantum information set decoding algorithms
• A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions
• Decoding quantum information via the Petz recovery map
• Syndrome Decoding Estimator
• Hybrid decoding -- classical-quantum trade-offs for information set decoding
• Memory-efficient quantum information set decoding algorithm
• Revisiting nearest-neighbor-based information set decoding
• Quantum sieving for code-based cryptanalysis and its limitations for ISD
• Reducing the number of qubits in quantum information set decoding
• A unified framework of quantum walk search

This page was built for publication: Improved quantum information set decoding

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