CryptoBook
Search…
Resources and notations

References/Resources

    1.
    Nguyen, P. Q., & Vallée, B. (Eds.). (2010). The LLL Algorithm. Information Security and Cryptography. doi:10.1007/978-3-642-02295-1
    Massive survey, lots of detail if you're extremely interested)
    2.
    May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. Universität Paderborn.
    Excellent exposition to LLL and coppersmith as well as showing some RSA attacks via LLL
    3.
    Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4), 515–534. doi:10.1007/bf01457454
    The original LLL paper, quite a nice read overall + proof that LLL works
    4.
    Coppersmith, D. (1996). Finding a Small Root of a Univariate Modular Equation. Lecture Notes in Computer Science, 155–165. doi:10.1007/3-540-68339-9_14
    5.
    Coppersmith, D. (1996). Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. Lecture Notes in Computer Science, 178–189. doi:10.1007/3-540-68339-9_16
    Both of these paper introduces the coppersmith algorithm as well as provide some examples
    6.
    Waerden, B. L. (1956). Die Reduktionstheorie Der Positiven Quadratischen Formen. Acta Mathematica, 96(0), 265–309. doi:10.1007/bf02392364

Notation

    LL
    lattice
      dim(L)\dim(L)
      dimension of lattice
      vol(L)\text{vol}(L)
      volume of lattice
    bib_i
    a chosen basis for
    LL
      B\mathcal B
      matrix whose
      ii
      th row vectors is
      bib_i
    bib_i^*
    Gram-Schmidt orthogonalization of
    bib_i
    (without normalization)
      B\mathcal B^*
      matrix whose
      ii
      th row vectors is
      bib_i^*
    μi,j=bi,bjbj,bj\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}
    Gram-Schmidt coefficients
    λi(L)\lambda_i(L)
    the
    ii
    th successive minima of
    LL
Last modified 5mo ago
Export as PDF
Copy link