Attacking Lattice-based Cryptography with Martin Albrecht

Security Cryptography Whatever

Returning champion Martin Albrecht joins us to help explain how we measure the security of lattice-based cryptosystems like Kyber and Dilithium against attackers. QRAM, BKZ, LLL, oh my!
Transcript: https://securitycryptographywhatever.com/2023/11/13/lattice-attacks/
Links:
- https://pq-crystals.org/kyber/index.shtml
- https://pq-crystals.org/dilithium/index.shtml
- https://eprint.iacr.org/2019/930.pdf
- https://en.wikipedia.org/wiki/Short_integer_solution_problem
- Frodo: https://eprint.iacr.org/2016/659
- https://csrc.nist.gov/CSRC/media/Events/third-pqc-standardization-conference/documents/accepted-papers/ribeiro-saber-pq-key-pqc2021.pdf
- https://en.wikipedia.org/wiki/Hermite_normal_form
- https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
- https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch18.pdf
- https://eprint.iacr.org/2019/1161
- QRAM: https://arxiv.org/abs/2305.10310
- https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
- MATZOV improved dual lattice attack: https://zenodo.org/records/6412487
- https://eprint.iacr.org/2008/504.pdf
- https://eprint.iacr.org/2023/302.pdf

"Security Cryptography Whatever" is hosted by Deirdre Connolly (@durumcrustulum), Thomas Ptacek (@tqbf), and David Adrian (@davidcadrian)

Chapters

1. Attacking Lattice-based Cryptography with Martin Albrecht (00:00:00)

2. Analyzing the Security of Post-Quantum Cryptography (00:00:12)

3. Finding Short Vectors in Lattices (00:13:13)

4. Quantum Speedup in Cryptography (00:19:11)

5. Understanding and Applying BKZ Algorithm (00:28:13)

6. Lattice-Based Cryptanalysis and Improvements (00:37:38)

7. RAM and Storage in Classical Attacks (00:46:57)

8. Discussion on AES Quantum Computing Costs (00:52:49)