Solving the learning parity with noise problem using quantum algorithms

DOI10.1007/978-3-031-17433-9_13MaRDI QIDQ6103086zbMATH OpenOpenAlexFDO

Authors Bénédikt Tran, Serge Vaudenay

Publication date 2 June 2023

Published in Progress in Cryptology - AFRICACRYPT 2022 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-17433-9_13

zbMATH Keywords

Gaussian eliminationLPNpost-quantum cryptographyWalsh-Hadamard transform

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Boolean and Hadamard matrices (15B34) Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Searching and sorting (68P10) Learning and adaptive systems in artificial intelligence (68T05) Quantum computation (81P68) Computational stability and error-correcting codes for quantum computation and communication processing (81P73) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Recommendations

• An improved quantum algorithm for the quantum learning with errors problem
• Quantum algorithms for the Goldreich-Levin learning problem
• Quantum learning algorithms for quantum measurements
• Improved bounds on quantum learning algorithms
• Quantum algorithm design using dynamic learning
• A strategy for quantum algorithm design assisted by machine learning
• Cryptography from learning parity with noise
• Quantum algorithms for learning and testing juntas
• Optimal quantum sample complexity of learning algorithms
• Optimal quantum sample complexity of learning algorithms

Cites work

• An Improved LPN Algorithm
• BKW meets Fourier new algorithms for LPN with sparse parities
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
• Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations
• Grover vs. McEliece
• scientific article; zbMATH DE number 4070796 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• LPN decoded
• Never Trust a Bunny
• Noise-tolerant learning, the parity problem, and the statistical query model
• On computing nearest neighbors with applications to decoding of binary linear codes
• On solving LPN using BKW and variants, Implementation and analysis
• Optimization of \(\mathsf {LPN}\) solving algorithms
• Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
• Quantum circuit for the fast Fourier transform
• Quantum computation and quantum information. 10th anniversary edition
• Quantum computing
• Quantum information set decoding algorithms
• Smaller decoding exponents: ball-collision decoding
• Solving LPN Using Covering Codes

Cited in

(3)

• LPN decoded
• An improved quantum algorithm for the quantum learning with errors problem
• Sample-size-reduction of quantum states for the noisy linear problem

This page was built for publication: Solving the learning parity with noise problem using quantum algorithms

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