Noise-tolerant learning, the parity problem, and the statistical query model
From MaRDI portal
Publication:5899519
DOI10.1145/792538.792543zbMath1325.68114OpenAlexW2065151783MaRDI QIDQ5899519
Hal Wasserman, Adam Tauman Kalai, Avrim L. Blum
Publication date: 12 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/792538.792543
Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60)
Related Items
Shortest vectors in lattices of Bai-Galbraith's embedding attack on the LWR problem ⋮ Cryptography from Learning Parity with Noise ⋮ Boolean ring cryptographic equation solving ⋮ On the Power of Learning from k-Wise Queries ⋮ Garbling XOR gates ``for free in the standard model ⋮ Coded-BKW: Solving LWE Using Lattice Codes ⋮ An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices ⋮ Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm ⋮ On a dual/hybrid approach to small secret LWE. A dual/enumeration technique for learning with errors and application to security estimates of FHE schemes ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions ⋮ Extracting Computational Entropy and Learning Noisy Linear Functions ⋮ A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme ⋮ \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Key-recovery attacks on \(\mathsf{ASASA}\) ⋮ Predicting the concrete security of LWE against the dual attack using binary search ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ Quantum learning Boolean linear functions w.r.t. product distributions ⋮ On the hardness of module learning with errors with short distributions ⋮ Polynomial‐time universality and limitations of deep learning ⋮ A subexponential-time, polynomial quantum space algorithm for inverting the CM group action ⋮ On the asymptotic complexity of solving LWE ⋮ Sample-size-reduction of quantum states for the noisy linear problem ⋮ Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds ⋮ Non-interactive secure computation of inner-product from LPN and LWE ⋮ Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms ⋮ Statistically sender-private OT from LPN and derandomization ⋮ Efficient authentication from hard learning problems ⋮ How to Encrypt with the LPN Problem ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ Algorithms for the approximate common divisor problem ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ A complete characterization of statistical query learning with applications to evolvability ⋮ A method of evaluating the security of Snow 2.0-like ciphers against correlation attacks over the finite extensions of two element field ⋮ Security estimates of a ring-LWE symmetric cryptosystem against chosen plaintext attack ⋮ Solving the learning parity with noise's open question ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ On the Complexity of Learning a Class Ratio from Unlabeled Data ⋮ A new birthday-type algorithm for attacking the fresh re-keying countermeasure ⋮ CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN ⋮ New Algorithms for Learning in Presence of Errors ⋮ On the complexity of the BKW algorithm on LWE ⋮ Improved Algorithms for the Approximate k-List Problem in Euclidean Norm ⋮ Some Recent Results on Local Testing of Sparse Linear Codes ⋮ Parallel and Concurrent Security of the HB and HB + Protocols ⋮ Homomorphic Evaluation Requires Depth ⋮ Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem ⋮ Improved learning of \(k\)-parities ⋮ An improved algorithm for learning sparse parities in the presence of noise ⋮ Parallel and concurrent security of the HB and \(HB^{+}\) protocols ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Quantum algorithms for algebraic problems ⋮ Solving LPN using covering codes ⋮ TFHE: fast fully homomorphic encryption over the torus ⋮ Breaking the circuit size barrier for secure computation under quasi-polynomial LPN ⋮ Generalized Learning Problems and Applications to Non-commutative Cryptography ⋮ Adventures in crypto dark matter: attacks and fixes for weak pseudorandom functions ⋮ How (Not) to Instantiate Ring-LWE ⋮ Cryptography with Auxiliary Input and Trapdoor from Constant-Noise LPN ⋮ Cryptography with constant input locality ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm ⋮ Hardness of learning problems over Burnside groups of exponent 3 ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ The Complexity of Public-Key Cryptography ⋮ Pseudorandom Functions: Three Decades Later ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms
This page was built for publication: Noise-tolerant learning, the parity problem, and the statistical query model
