Questions tagged [lenstra-lenstra-lovasz]

The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm efficiently finds a short, nearly orthogonal lattice basis form an arbitrary one

Filter by
Sorted by
Tagged with
0
votes
0answers
28 views

Size upper bound on LLL-reduced basis

Suppose $\Lambda$ is a lattice in $\mathbb{Z}^m$ and let $\{b_1, ..., b_n\}$ be an LLL-reduced basis, rename these vectors as $v_1, ... , v_n$ such that $1 \leq ||v_1|| \leq ... \leq ||v_n||$. How can ...
3
votes
0answers
63 views

Gram-Schmidt coefficients in LLL algorithm

To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the ...
7
votes
1answer
440 views

Introduction to LLL algorithm applied to linear modular inequalities

What is the Lenstra–Lenstra–Lovász lattice basis reduction algorithm about? How is it applied to solve for $x\pmod m$ a system of modular inequalities $(u_i\,x+v_i\bmod m)<w$ for $0\le i<n$? I'm ...
3
votes
1answer
121 views

Lattice reduction question regarding the capability of LLL and BKZ

I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things. LLL algorithm runs in polynomial time, but isn't capable of ...
3
votes
1answer
247 views

LLL - Lattice Reduced Basis Algorithm question?

I have two related questions: Version 1: Let $B=\{b_1,b_2,\dots,b_n\}$ be an orthogonal basis for $R^n$. What is the associated reduced basis obtained by applying LLL algorithm to $B$? I know how ...
1
vote
0answers
63 views

What is the minimal angle between two LLL reduced vectors?

What is the minimal angle between two LLL reduced vectors? It seems it should be 60 degree as $|\mu_{i,j}| \leq \frac{1}{2}$. If we make the upper bound of $\mu_{i,j}$ by 1/3, can we get better ...
4
votes
1answer
197 views

$L^3$ Grover search of NTRU variants

I was reading a text on cryptology by Wayne Patterson and came across the $L^3$ algorithm which reduces integer lattices with respect to their base. I've also read on the NIST CFP A8 that attacks ...
4
votes
1answer
638 views

Significance of Gram-Schmidt coefficients in LLL algorithm

Let $\{ {\bf v}_1,{\bf v}_2 \}$ be two linearly independent vectors. An orthogonal base $\{{\bf u}_1,{\bf u}_2 \}$ of the vector space $\mathrm{span}\{ {\bf v}_1,{\bf v}_2 \}$ can be computed using ...
7
votes
1answer
1k views

Why is the Lovász condition used in the LLL algorithm?

The LLL algorithm is used to approximate the Shortest Vector Problem, i.e., it outputs a reduced basis. Such a basis will satisfy two conditions: $$ \forall i \gt j. \quad \lvert\mu_{ij}\rvert \le \...
9
votes
1answer
2k views

Problem with LLL reduction on truncated LCG schemes

I am struggling to apply Freize et al. paper to break a truncated LCG. A truncated LCG is a pseudo random generator that outputs the $n$ leading bits $y_i$ of $x_i$, where $(x_i)$ is such that $x_{...