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

quantum walknear neighbourinformation set decoding

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)

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

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)