Lattices with Symmetry

on YouTube ↗44m

" summary

Gives a concrete deterministic polynomial-time algorithm that decides whether a lattice with a fixed finite abelian symmetry group G is G-isomorphic to the standard G-lattice and, when so, constructs the isomorphism (equivalently finds an orthonormal basis). Method translates Gentry–Zidlow into graded tensor algebras, replaces heuristic primes by provable auxiliary prime powers via analytic number theory, and extracts short vectors using LLL plus commutative-algebra routines; algorithm is proven correct and polynomial-time, not yet implemented.

AI-written summary · about

" chapters (16)

1. 0:00Introduction and logistics
2. 0:33Conference announcement
3. 1:40Motivation for the research
4. 2:44Overview of lattice schemes
5. 5:40Decryption processes
6. 8:24Addressing decryption failures
7. 11:51Gentry-Szydlo algorithm
8. 14:28Understanding the algorithm
9. 18:14Mathematical innovations
10. 21:53Lattice symmetry definitions
11. 24:52Examples of G-lattices
12. 28:51Main algorithm statement
13. 32:19Connecting to Gentry-Szydlo
14. 34:48Algorithmic steps and theory
15. 38:09Future work and conclusion
16. 43:25Q&A session

" related talks

• 01h 42mMathematics of LatticesDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 08mThe Mathematics of Lattices IVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 01h 04mThe Mathematics of Lattices IIVinod Vaikuntanathan · Cryptography Boot Camp 2015
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 02mLattice TrapdoorsShweta Agrawal · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 00mMultilinear Maps and Attacks ISanjam Garg · Cryptography Boot Camp 2015