4 ms·

Building lattice reduction (LLL) intuition

81 points by kkl 9y ago

abetusk 9y ago
For context, LLL was used to prove that polynomial factorization can be solved in polynomial time. That is, given r(x) such that: r(x) = p(x) * q(x) where the coefficients of each factor are integral: p_i, q_i in Z LLL can be used to find p(x) and q(x) only given r(x). There are other problems that LLL solves and there are more modern lattice reduction algorithms (PSLQ, etc.) but LLL was one of the first.
- cperciva 9y ago
  There are other problems that LLL solves My favourite is integer relationship finding. For example, if you stumble across the value 194.927424491 it's straightforward to figure out that it is pi * 23 + e * 29 + sqrt(2) * 31.
  - aruss 9y ago
    So, solving CVP? That's a pretty neat application, though.
    - pbsd 9y ago
      The typical way you'd solve that would be to take [K * pi 1 0 0] [K * e 0 1 0] [K * sqrt(2) 0 0 1] [K * 194.927424491 0 0 0] for some large-ish K, say 2^20, and look for a short(est) vector of this lattice. Basically you're minimizing the norm of (a * pi + b * e + c * sqrt(2) + d * 194.927424491, a, b, c) while giving the majority of the weight to the first component, which you hope to be near 0.
      - cperciva 9y ago
        look for a short(est) vector of this lattice Just to elaborate slightly on this: Finding the shortest vector in a lattice is (in general) hard, but finding a vector which is no more than a constant times the length of the shortest vector is easy. So techniques which rely on lattice reduction usually construct a lattice such that the shortest vector is much shorter than the second-shortest vector -- in other words, the shortest vector is the only one which satisfies the "no more than X times the length of the shortest vector" condition. In the case of integer relation finding, this translates into having enough digits and making the value K large enough.
tptacek 9y ago
This is probably my favorite crypto blog post of the year. LLL comes up a lot in attacks on asymmetric cryptography. If you're interested in crypto or linear algebra but don't know what a lattice is, a great starting point is Hoffstein's _Introduction to Mathematical Cryptography_: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.9999&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182... (If you know what a vector space is, you know what a lattice is; it's a vector space where only integers are allowed as coefficients in linear combinations). Here's Antoine Joux, one of the world's most renowned cryptanalysts, talking about applications of LLL to crypto attacks. Amusingly, he sort of opens by making fun of cryptographers for using LLL without really understanding it: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7624 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7... Here's Babai's application of LLL to finding close lattice points: http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20lattice%20reduction%20and%20the%20nearest%20lattice%20point%20problem.pdf http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20la... From here you're a [boneh hidden number problem] Google search away from attacking dlog/ecdlog crypto from vulnerabilities like biased nonces.
- aruss 9y ago
  To add to your post, lattice attacks (LLL/BKZ/etc) are becoming even more prevalent in cryptanalysis as they are the best known attacks against next-gen cryptosystems like NTRU, or anything based on the Learning-with-Errors problem, which includes schemes with "fun" properties like full P/poly homomorphism, attribute/predicate encryption, etc.

81 points by kkl 9y ago

For context, LLL was used to prove that polynomial factorization can be solved in polynomial time. That is, given r(x) such that: r(x) = p(x) * q(x) where the coefficients of each factor are integral: p_i, q_i in Z LLL can be used to find p(x) and q(x) only given r(x). There are other problems that LLL solves and there are more modern lattice reduction algorithms (PSLQ, etc.) but LLL was one of the first.

cperciva 9y ago
There are other problems that LLL solves My favourite is integer relationship finding. For example, if you stumble across the value 194.927424491 it's straightforward to figure out that it is pi * 23 + e * 29 + sqrt(2) * 31.
- aruss 9y ago
  So, solving CVP? That's a pretty neat application, though.
  - pbsd 9y ago
    The typical way you'd solve that would be to take [K * pi 1 0 0] [K * e 0 1 0] [K * sqrt(2) 0 0 1] [K * 194.927424491 0 0 0] for some large-ish K, say 2^20, and look for a short(est) vector of this lattice. Basically you're minimizing the norm of (a * pi + b * e + c * sqrt(2) + d * 194.927424491, a, b, c) while giving the majority of the weight to the first component, which you hope to be near 0.
    - cperciva 9y ago
      look for a short(est) vector of this lattice Just to elaborate slightly on this: Finding the shortest vector in a lattice is (in general) hard, but finding a vector which is no more than a constant times the length of the shortest vector is easy. So techniques which rely on lattice reduction usually construct a lattice such that the shortest vector is much shorter than the second-shortest vector -- in other words, the shortest vector is the only one which satisfies the "no more than X times the length of the shortest vector" condition. In the case of integer relation finding, this translates into having enough digits and making the value K large enough.

tptacek 9y ago

This is probably my favorite crypto blog post of the year. LLL comes up a lot in attacks on asymmetric cryptography. If you're interested in crypto or linear algebra but don't know what a lattice is, a great starting point is Hoffstein's _Introduction to Mathematical Cryptography_: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.9999&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182... (If you know what a vector space is, you know what a lattice is; it's a vector space where only integers are allowed as coefficients in linear combinations). Here's Antoine Joux, one of the world's most renowned cryptanalysts, talking about applications of LLL to crypto attacks. Amusingly, he sort of opens by making fun of cryptographers for using LLL without really understanding it: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7624 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.7... Here's Babai's application of LLL to finding close lattice points: http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20lattice%20reduction%20and%20the%20nearest%20lattice%20point%20problem.pdf http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20lovasz%20la... From here you're a [boneh hidden number problem] Google search away from attacking dlog/ecdlog crypto from vulnerabilities like biased nonces.

aruss 9y ago
To add to your post, lattice attacks (LLL/BKZ/etc) are becoming even more prevalent in cryptanalysis as they are the best known attacks against next-gen cryptosystems like NTRU, or anything based on the Learning-with-Errors problem, which includes schemes with "fun" properties like full P/poly homomorphism, attribute/predicate encryption, etc.