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
13
questions
0
votes
1answer
39 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 ...
2
votes
0answers
65 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 ...
0
votes
0answers
46 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 ...
0
votes
0answers
33 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
71 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 ...
8
votes
1answer
625 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
159 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
273 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
67 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 ...
5
votes
1answer
217 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
691 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
2k 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_{...
Hot Network Questions
- What navigation actions does a pilot take when simply told to "go around"?
- Offer subject to survey or survey before an offer?
- How is c4 the best move in this position?
- What is the need for a "related work" section in state-of-the-art papers?
- How can I make a tracing game mechanic more engaging?
- How to separate wood I glued together
- Menger's theorem with restrictions on where the paths can begin and end
- Can I book a flight USA-A-B and get off at A, if I don't have a visa for country B?
- What can you do when a driver cuts you off?
- How can I solve a linear optimization problem with bounds that are a function of the decision
- Why is 10 missing in NEMA nomenclature
- Is there a difference between marginal likelihood and likelihood of a marginal distribution?
- What is sfc in sf Package of R?
- Ahmaud Arbery defendants invoke Georgia State Law as a Defense in Federal Court
- loop through one file extension or the other in bash or zsh
- Is putting cold milk foam on hot coffee unsafe?
- Can I say "I live in the countryside" if I live in the urban area of a small, remote city?
- Novel with a paid assassin who travels with a variety of older companions
- Volvo engine parts
- Why does the mixture knob spin?
- Why do people Shadowbox without full extension?
- Can you make a plywood jigsaw puzzle, using a jigsaw power tool?
- Throw exception if value is not found
- Cannot remove write protection from USB drive