2 unstable releases
0.2.0 | Apr 6, 2020 |
---|---|
0.1.0 | Feb 22, 2020 |
#637 in Math
34KB
670 lines
lll-rs
lll-rs
is an implementation of the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL [LLL82], 1a, 1b) in Rust.
Supported algorithms
The library comes with a set of simple helpers to create vectors and matrices, with the following entries:
- Integers (
BigVector
, relying onrug::Integer
) - Rationals (
RationalVector
, relying onrug::Rational
) - Small rationals (
VectorF
, relying onf64
)
lll-rs
is far from feature-complete and should be considered experimental. Users willing to use a stable and battle-tested library should
consider fplll
instead fplll.
Lattice reduction
A lattice Λ is a dicrete subgroup of some vector space E. A typical example (see e.g. 3) is E = ℝⁿ and
X ∊ Λ <=> X = l_1 * b_1 + ... + l_n * b_n with (l_i) in ℤ and (b_i) in ℝ
Lattices are much studied mathematical structures on which we can formulate some useful problems 4. Some of these problems are simpler to solve when a "good basis" is known for the lattice. Conversely it is difficult to solve them when only a "bad basis" is known.
Simply put, the LLL algorithm provides such a "good basis"; it roughly does so by performing a (variant of) rounded Gram-Schimdt orthogonalization on the "bad basis". Remarkably, this algorithm runs in polynomial time which makes it possible to solve several lattice problems efficiently.
Applications of LLL include:
- Cryptanalysis of lattice-based cryptosystems (e.g. NTRU)
- Cryptanalysis of pseudo-random number generators (e.g. LCG and truncated LCG)
- Cryptanalysis of RSA (e.g. Coppersmith's attack 5)
- Cryptanalysis of knapsack-based cryptosystems
- Finding mathematical counterexamples (e.g. Merten's conjecture)
- Finding roots of polynomials with integer coefficients
- Finding integer relations between constants
- Decoding of error correcting codes
Example
// Init the matrix with Integer
let mut basis: Matrix<BigVector> = Matrix::init(3, 4);
// Populate the matix
basis[0] = BigVector::from_vector(vec![
Integer::from(1) << 100000,
Integer::from(0),
Integer::from(0),
Integer::from(1345),
]);
basis[1] = BigVector::from_vector(vec![
Integer::from(0),
Integer::from(1),
Integer::from(0),
Integer::from(35),
]);
basis[2] = BigVector::from_vector(vec![
Integer::from(0),
Integer::from(0),
Integer::from(1),
Integer::from(154),
]);
// Perfom the LLL basis reduction
biglll::lattice_reduce(&mut basis);
// OR
// Perfom the L2 basis reduction
// Specify the delta and eta coefficient for the reduction
bigl2::lattice_reduce(&mut basis, 0.5005, 0.999);
References and documentation
[LLL82] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann., 261: 515–534 (1982)
- https://openaccess.leidenuniv.nl/bitstream/handle/1887/3810/346_050.pdf
- https://en.wikipedia.org/wiki/Lenstra–Lenstra–Lovász_lattice_basis_reduction_algorithm
- https://perso.ens-lyon.fr/damien.stehle/downloads/LLL25.pdf
- https://en.wikipedia.org/wiki/Lattice_(group)
- https://en.wikipedia.org/wiki/Lattice_problem
- https://en.wikipedia.org/wiki/Coppersmith%27s_attack
Dependencies
~2.5MB
~47K SLoC