New Algorithms for Learning in Presence of Errors

By Sanjeev Arora, Rong Ge. 2011

313 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

XPIR : Private Information Retrieval for Everyone (2016, background): “As number theoretic approaches failed to provide efﬁcient cPIR schemes, some alternatives were explored [6, 7, 8], but all of them were based on non-standard problems and have been broken [9, 10, 11, 12, 13].”
Multiparty Computation from Somewhat Homomorphic Encryption (2012, background): “In [1] the authors present a combinatorial attack which breaks LWE in time 2O(‖e‖ 2 ∞) with high probability.”
Simple Encrypted Arithmetic Library - SEAL v2.1 (2016, background): “estimator was not run for Arora-Ge type attacks [8, 4] or for meet-inthe-middle type attacks, since these are both expected to be very costly.”
Pseudorandom Functions and Lattices (2012, background): “We note that although our proof uses a super-polynomial q = n, as long as q/p ≥ √ n is an integer, the LWR problem appears to be exponentially hard (in n) for any p = poly(n), and super-polynomially hard for p ≤ 2 for any < 1, given the state of the art in noisy learning algorithms [8, 5] and lattic”
Lattice Signatures Without Trapdoors (2012, methodology): “But in view of the recent algorithm of Arora and Ge [5], which uses algebraic attacks to attack the LWE problem with very small errors, there may be reasons to think that the instantiation in column V could be more secure because it uses larger coefficients.”
Compressible FHE with Applications to PIR (2019, background): “)10 The entries of the Eu’s can be chosen from a distribution of variance 8 (which is good enough to avoid the Arora-Ge attacks [5]).”
Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems (2012, methodology): “2 For readers familiar with the Arora-Ge algorithm for solving LWE with small noise [2], we would like to point out that it is does not apply to our problem because this algorithm requires polynomially-many samples of the form (ai,ais+ ei), whereas in our problem, only one such sample is given.”
Post-quantum Key Exchange - A New Hope (2016, background): “In particular, because there are only m = n samples available one may rule out BKW types of attacks [53] and linearization attacks [6].”
Pseudorandom Functions: Three Decades Later (2017, background): “Moreover, known attacks using lattice basis reduction [89, 130] or combinatorial/algebraic methods [37, 13] require time 2Ω̃(n/ log(1/α)).”
Hardness of SIS and LWE with Small Parameters (2013, methodology): “This qualification is necessary in light of the Arora-Ge attack [2], which for large enough m can solve LWE with binary errors in polynomial time.”
Homomorphic Encryption (2017, unknown): “Also we clearly need αq ≥ 1 (else the only integer vector satisfying ‖~η‖∞ ≤ αq is the all-zero vector), and there are attacks due to Arora and Ge [5] that apply when αq = O(1).”
Computational Limitations in Robust Classification and Win-Win Results (2019, methodology): “For structured LPN samples, more efficient algorithms are known Arora and Ge (2011). Our error distributions are not structured.”
CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme (2018, methodology): “For our parameters, the BKW [BKW03] and Arora–Ge [AG11] families of algorithms are far from competitive.”
Software Speed Records for Lattice-Based Signatures (2013, methodology): “Therefore, the DCK problem is an ”aggressive” variant of the LWE problem but is not affected by the Arora-Ge algorithm as only one sample is given for the DCK problem and not the required polynomially-many [1].”
On the concrete hardness of Learning with Errors (2015, methodology): “Arora and Ge proposed an alternative approach to solving Search-LWE by setting up a system of noise-free non-linear polynomials of which the secret s is a root [12].”
Simple Encrypted Arithmetic Library-SEAL (2017, background): “estimator was not run for Arora-Ge type attacks [8, 4] or for meet-inthe-middle type attacks, since these are both expected to be very costly.”