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
2 votes
1 answer
78 views

Algorithm to solve SVP (shortest vector problem) using LLL reduction

I'm trying to write a C++ program to solve the shortest vector problem. The program is given a basis of a vector space V and needs to find the shortest non-zero vector in V. Right now I'm using the ...
Valéry Giscard d'Estaing's user avatar
0 votes
0 answers
46 views

Does randomization make a big difference in the output of the BKZ algorithm?

We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some ...
constantine's user avatar
2 votes
1 answer
109 views

LLL on Knapsack-eque problem

Given integers $s_1, \dots , s_n$ and target integer $t$, I'm trying to find small integer coefficients $x_1, \dots , x_n$ such that: $$ t \approx x_1 s_1 + \dots +x_ns_n $$ Taking inspiration from ...
user348382's user avatar
3 votes
1 answer
180 views

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
  • 75
1 vote
2 answers
147 views

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
2 votes
2 answers
286 views

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
260 views

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
132 views

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
67 views

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
89 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 ...
Severin's user avatar
  • 31
9 votes
1 answer
2k 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 ...
fgrieu's user avatar
  • 140k
3 votes
1 answer
569 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 ...
DannyNiu's user avatar
  • 9,080
3 votes
1 answer
445 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 ...
esra's user avatar
  • 869
1 vote
0 answers
94 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 ...
user15864's user avatar
  • 219
5 votes
1 answer
274 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 ...
floor cat's user avatar
  • 214
5 votes
1 answer
936 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 ...
preethi's user avatar
  • 889
10 votes
2 answers
3k 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 \...
preethi's user avatar
  • 889
9 votes
1 answer
4k 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_{...
Mariuslp's user avatar
  • 285