Using Lattices for Cryptanalysis
summary
Lattice reduction using LLL and BKZ yields practical cryptanalysis: lattices up to a few thousand dimensions run (a reported 4096-dim / 6000-bit in four days result is parallel and not released), while 250-dim BKZ reaches near-exact SVP. Coppersmith’s method is provable for small roots (roughly N^{1/d}), and recovers RSA when messages or key fragments are small (half of p’s bits → factor; d < N^{1/4} or Boneh–Durfee’s ~N^{0.292} bounds). Multivariate and ring instances remain heuristic and ad hoc; ECDSA/hidden-number attacks succeed when nonces leak MSBs.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:16Talk outline: Breaking classical crypto with lattices
- 0:59Warm-up 1: Solving knapsack problems with lattices
- 3:29Practical note: Current feasible lattice reduction
- 8:41Warm-up 2: Lattice attacks on NTRU
- 13:37Coppersmith's method for univariate polynomials
- 19:10Coppersmith's Algorithm Outline
- 23:21Coppersmith's method outline
- 36:41Finding solutions modulo divisors
- 49:02Multivariate Coppersmith
- 51:17Application: Approximate common divisors
related talks
01h 40mHistorical Talk on Lattice-Based Cryptography
39mLattice Based Cryptography Primer
57mChallenges in Evaluating Costs of known Lattice Attacks
01h 08mCryptography from Ideal Lattices
41mLattice based cryptography
30mOn the Concrete Security of LWE with Small Secret
52mAn LLL Algorithm for Module Lattices
40mPost-Quantum