As of May 31, 2023, we have updated our Code of Conduct.

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
3 votes
1 answer

How does the lengths of the Gram-Schmidt orthogonal basis of a lattice basis change after lll reduction?

Assuming there is a lattice basis $B=\{b_1,...,b_n\}$, we use $B^*=\{b_1^*,...,b_n^*\}$ to denote the Gram-Schmidt orthogonal basis, where $b_i^*=\pi_i(b_i)$ and $\pi_i(b_i)$ denotes the projection of ...
kangli's user avatar
  • 65
1 vote
2 answers

How "unorthogonal" can a LLL-reduced basis be?

I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
haoyu's user avatar
  • 21
0 votes
0 answers

Finding small roots of a univariate polynomial modulo N. Don Coppersmith

I'm currently trying to understand the Coppersmith's method of finding small integer roots of polynomials modulo some integer. I am reading the original paper Small Solutions to Polynomial Equations, ...
SarkoxedaF's user avatar
2 votes
2 answers

Example of bad basis for lattices (worst-case for LLL)

Summary. Given some dimension $n$ (say $n=50$), is it possible to describe explicitly a lattice $L$ and a basis $B$ of $L$ such that $$ \frac{ \| LLL(B)_1 \| }{ \lambda_1(L) } > 1.02^n $$ where $...
Watson's user avatar
  • 151
0 votes
1 answer

NTL: Solve the closest vector problem for non-square matrix using LLL/Nearest Plane Algorithm

Assume I have a matrix $A \in \mathbb{Z}^{m \times n}$, $m > n$, which forms a basis of a lattice. Given a vector target vector $t = Ax + e$, $t,e \in \mathbb{Z}^m$,$x \in \mathbb{Z}^n$, I want to ...
cryptobeginner's user avatar
2 votes
0 answers

Howgrave-Graham lattice attack on NTRU

I am lookin for a good example to illustrate this attack on NTRU using low parameters but I failed to do that, The attack consist to use LLL reduction on A basis of NTRU Lattice, let us use the column ...
Don Freecs's user avatar
0 votes
0 answers

Gram-Schmidt upper triangular basis

I'm trying to understand the Gram-Schmidt Orthogonalization process. Below, there is an explanation that a lattice basis can be described by an upper triangular vector. It is often convenient to ...
Semiramis's user avatar
3 votes
0 answers

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 ...
Severin's user avatar
  • 31
8 votes
1 answer

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 ...
fgrieu's user avatar
  • 134k
3 votes
1 answer

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 ...
DannyNiu's user avatar
  • 8,291
3 votes
1 answer

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 ...
esra's user avatar
  • 879
1 vote
0 answers

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 ...
user15864's user avatar
  • 219
5 votes
1 answer

$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 ...
floor cat's user avatar
  • 214
5 votes
1 answer

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 ...
preethi's user avatar
  • 879
10 votes
2 answers

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 \...
preethi's user avatar
  • 879
9 votes
1 answer

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_{...
Mariuslp's user avatar
  • 285