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.

Intro
Timed Cryptography
Hardness vs Fine-Grained Hardness
Landscape of Sequential Problems
Enter Quantum Computing
A New Sequential Function
The Sequentiality Assumption
Evidence of Sequentiality
Proofs of Sequential Work
Self-Symmetry
The Protocol (Step 2)
Soundness
Open Problems
Lattice Cryptanalysis
Hints [DDGR20]
Limitations [DDGR20]
Objectives
Basic Concepts
The DBDD Problem
Towards a New Approach
What do we Obtain?
Integrating Hints Geometrically
Perfect Hints
Ellipsoid Method a
Revisiting Decryption Failures
Full Sized Decryption Failures
Geometric Failure Boosting
Combined Hints
Discussion and Future Work