CSE 291, Spring 2024
Cryptanalysis


Instructor:
  Nadia Heninger (nadiah at cs dot ucsd dot edu)

TA:
  Keegan Ryan  

Lectures:
  Tuesday/Thursday 2pm-3:20pm EBU3B 4258


Course Overview

This is a graduate-level special topics course on public-key cryptanalysis. Students will read and present research papers and carry out a quarter-long research project.

Prerequisites: CSE 207A or CSE 207B, background in number theory, or instructor permission.


Tentative Schedule

Reading Additional papers
4/2 Introduction and Planning Reconstructing RSA private keys from random key bits
Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
Using LLL-Reduction for Solving RSA and Factorization Problems
4/4 Recovering cryptographic keys from partial information, by example The Geometry of Syzygies
The Generalized Basis Reduction Algorithm
4/9 On Bounded Distance Decoding with Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem Reference repository on Lattice-based Cryptography
A Persional view of Average-case Complexity
Lattice Blog Reduction - Part 1: BKZ
A riddle wrapped in an enigma
4/11 Lattice attacks on NTRU and LWE: A History of Refinements
4/16 No class
4/18 No class
4/23 Lattices with Symmetry
4/25 Finding short integer solutions when the modulus is small
4/30 No class
5/2 No class
5/7 A Tale of Two Sieves
5/9 Comparing the Difficulty of Factorization and Discrete Logarithm: a 240-digit Experiment
5/14 Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
5/16 When eth Roots Become Easier than Factoring
5/21 Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations
5/23 Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA
5/28 Project presentations
5/30 Project presentations
6/4 Project presentations
6/6 Project presentations

Open/research problems

  1. Implement the Lovasz generalized basis reduction algorithm. Perhaps experiment with a better norm for polynomial evaluation.
  2. Implement baby step giant step discrete log for multiple chunks of missing exponents. Does it work as expected?