Attacks on the Search RLWE Problem with Small Errors
From MaRDI portal
Abstract: The Ring Learning-With-Errors (RLWE) problem shows great promise for post-quantum cryptography and homomorphic encryption. We describe a new attack on the non-dual search RLWE problem with small error widths, using ring homomorphisms to finite fields and the chi-squared statistical test. In particular, we identify a "subfield vulnerability" (Section 5.2) and give a new attack which finds this vulnerability by mapping to a finite field extension and detecting non-uniformity with respect to the number of elements in the subfield. We use this attack to give examples of vulnerable RLWE instances in Galois number fields. We also extend the well-known search-to-decision reduction result to Galois fields with any unramified prime modulus q, regardless of the residue degree f of q, and we use this in our attacks. The time complexity of our attack is O(nq2f), where n is the degree of K and f is the residue degree of q in K. We also show an attack on the non-dual (resp. dual) RLWE problem with narrow error distributions in prime cyclotomic rings when the modulus is a ramified prime (resp. any integer). We demonstrate the attacks in practice by finding many vulnerable instances and successfully attacking them. We include the code for all attacks.
Recommendations
- Attacks on Integer-RLWE
- Practical analysis of key recovery attack against search-LWE problem
- Practical attacks on small private exponent RSA: new records and new insights
- A unified framework for small secret exponent attack on RSA
- Public Key Cryptography - PKC 2006
- On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL
- Attacks on multi-prime RSA with small prime difference
- Integer LWE with non-subgaussian error and related attacks
- Predicting the concrete security of LWE against the dual attack using binary search
- The Wiener attack on RSA revisited: a quest for the exact bound
Cites work
- (Leveled) fully homomorphic encryption without bootstrapping
- A new test for randomness and its application to some cryptographic problems
- Efficient fully homomorphic encryption from (standard) LWE
- Fully homomorphic encryption from ring-LWE and security for key dependent messages
- Fully homomorphic encryption with polylog overhead
- How (not) to instantiate ring-LWE
- scientific article; zbMATH DE number 1418301 (Why is no real title available?)
- Improved security for a ring-based fully homomorphic encryption scheme
- Lattice-based Cryptography
- Making NTRU as secure as worst-case problems over ideal lattices
- New Algorithms for Learning in Presence of Errors
- On error distributions in ring-based LWE
- On ideal lattices and learning with errors over rings
- On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
- Provably weak instances of Ring-LWE
- Provably weak instances of ring-LWE revisited
- Ring-LWE in polynomial rings
- Trapdoors for hard lattices and new cryptographic constructions
- Weak instances of PLWE
- Worst-case to average-case reductions for module lattices
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Cited in
(17)- On the ring-LWE and polynomial-LWE problems
- Security considerations for Galois non-dual RLWE families
- Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices
- LWE from non-commutative group rings
- Rounding in the rings
- Ring-LWE cryptography for the number theorist
- Error analysis of weak poly-LWE instances
- Provably weak instances of ring-LWE revisited
- Algebraic aspects of solving ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
- Homomorphic Encryption Standard
- Attacks on Integer-RLWE
- RLWE/PLWE equivalence for the maximal totally real subextension of the \(2^rpq\)-th cyclotomic field
- On the weakness of ring-LWE mod prime ideal \(\mathfrak{q}\) by trace map
- Learning with errors over group rings constructed by semi-direct product
- Spectral distortion and the ring learning with errors problem
- Cryptanalysis of plwe based on zero-trace quadratic roots
- A generalized approach to root-based attacks against PLWE
This page was built for publication: Attacks on the Search RLWE Problem with Small Errors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603026)
