Crypto 2023 Best Paper Plenary - Fast Lattice Reduction and Adaptive Schnorr Signatures

Explore the cutting-edge advancements in cryptography presented at the Crypto 2023 Best Paper Plenary session, chaired by Helena Handschuh. Delve into two groundbreaking papers: "Fast Practical Lattice Reduction through Iterated Compression" by Keegan Ryan and Nadia Heninger, and "Fully Adaptive Schnorr Threshold Signatures" by Elizabeth Crites, Chelsea Komlo, and Mary Maller. Learn about the latest developments in lattice reduction techniques, their applications in cryptanalysis, and the challenges of implementing fast and numerically stable algorithms. Discover the importance of Schnorr signatures, threshold signatures, and the complexities of achieving concurrent adaptive security in multi-party signature schemes. Gain insights into topics such as q-ary lattices, Gentry-Halevi FHE, RSA partial factorization, and the intricacies of ROS attacks. This 52-minute plenary session offers a comprehensive overview of cutting-edge research in cryptography, providing valuable knowledge for both experts and enthusiasts in the field.

Intro
The "Two Faces" of lattice reduction [NS01]
Lattice reduction is a cryptanalytic bottleneck
Example: Gentry-Halevi FHE [GH11]
LLL reduction finds a good basis
Fast lattice reduction strategies
Towards faster lattice reduction [KEF21]
Lattice basis compression [SMSV14]
Lattice reduction with iterated compression
Is our algorithm numerically stable?
Is our algorithm fast?
Implementation - flatter
Experiment: q-ary lattices
Experiment: Gentry-Halevi FHE [GH11]
Experiment: RSA partial factorization [How01]
Further applications
Why Schnorr signatures?
What are threshold signatures?
Why multi-party Schnorr signatures? Why
Main Goals
2-Round Threshold Scheme
Concurrent Security: ROS Attacks NKDMOS
Recent Schnorr Threshold Signatures
Concurrent Adaptive Security
Adaptive Security is Challenging
Sparkle
Adaptive Security under (A)OMDL
Key Takeaways