Attacks on Ring-LWE

on YouTube ↗38m

" summary

Paper shows practical attacks on decision RLWE instances that come from PLWE-style errors when the defining polynomial has a root mod q or a small-order root; it uses the change-of-basis spectral norm to predict how the coefficient-wise Gaussian error is distorted and to select vulnerable fields. Implementations in Sage recover secrets for TLS-like parameters (example run finishes in 13.5 hours with ~20 samples) and break smaller parameter sets in seconds; attack loops over guesses mod q so cost scales roughly O(q).

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 0:38Homomorphic Encryption
3. 2:35LWE and Ring LWE
4. 4:43Hardness Assumptions
5. 6:06Embeddings and PLWE
6. 8:30Error Distribution
7. 10:39Attack Overview
8. 13:08Attack Mechanisms
9. 15:13Required Properties
10. 17:56Attack Extensions
11. 20:55Weak RLWE Fields
12. 23:26Construction Theorem
13. 25:10Parameter Selection
14. 28:56Experimental Results
15. 31:00Number Theory Problems
16. 32:47Q&A

" related talks

• 01h 28mThe Learning With Errors Problem and Cryptographic ApplicationsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 15mAlgebraic Lattices and Ring Learning with ErrorsChris Peikert · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 30mOn the Concrete Security of LWE with Small SecretLynn Chua · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 31mIdentity-Based EncryptionParhat Abla, Huiwen Jia · RSA Conference 2024
• 56mContinuous LWE is as Hard as LWENeekon Vafa · Quantum and Lattices Joint Reunion Workshop
• 39mLattice Based Cryptography PrimerBob Relyea · DevConf.CZ 2021
• 21mQuantum Proofs of Deletion for Learning with ErrorsAlexander Poremba · ITCS 2023