1 of 17

Lec 4: Lattice Basis Reduction and�Finding Small Roots

2 of 17

  •  

3 of 17

Lattices

4 of 17

  •  

5 of 17

Some basic facts about lattices

  •  

6 of 17

  •  

7 of 17

LLL reduction

  •  

8 of 17

Finding Small Roots�(Coppersmith’s Method)

9 of 17

  •  

10 of 17

Howgrave-Graham’s condition

  •  

11 of 17

Basic idea

  •  

12 of 17

  •  

13 of 17

  •  

14 of 17

  •  

15 of 17

Better result [Coppersmith96]

  •  

16 of 17

References

  • [LLL82] Arjen K. Lenstra, Jan Karel Lenstra, and László Lovász. Factoring Polynomials with Rational Coefficients. In Mathematische Annalen 261(4).
  • [Håstad85] Johan Håstad. On Using RSA with Low Exponent in a Public Key Network. In CRYPTO 1985.
  • [Coppersmith96] Don Coppersmith. Finding a Small Root of a Univariate Modular Equation. In EUROCRYPT 1996.
  • [Howgrave-Graham97] Nick Howgrave-Graham. Finding Small Roots of Univariate Modular Equations Revisited. In IMACC 1997.

17 of 17

  • [NS05] Phong Q. Nguyễn and Damien Stehlé. Floating-Point LLL Revisited. In EUROCRYPT 2005.