Lattice Problems and Their Complexity - Crypto 2023 Session 2

Explore a comprehensive session from Crypto 2023 on lattice problems and their complexity, chaired by Chris Peikert. Delve into topics such as timed cryptography, hardness vs fine-grained hardness, sequential problems, quantum computing implications, and a new sequential function. Examine the sequentiality assumption, evidence of sequentiality, proofs of sequential work, and self-symmetry. Investigate lattice cryptanalysis, including hints and limitations from [DDGR20], basic concepts, the DBDD problem, and new approaches. Learn about integrating hints geometrically, perfect hints, and the ellipsoid method. Revisit decryption failures, including full-sized failures and geometric failure boosting. Conclude with a discussion on combined hints and future research directions in this critical area of cryptography.