7
$\begingroup$

This may be too broad question but it is not. I have been studying lattices for few months now, more specifically I studied:

  1. lattice problems ($SVP$, $CVP$ and etc.)
  2. lattice cryptography in post quantum computers
  3. worst-case hardness in lattice cryptography
  4. public key encryption using lattice
  5. lattice reduction algorithms (LLL and it's running time)

However, I could not figure out the relationship with reducing a lattice basis and lattice problems. Essentially, why we should reduce a lattice basis? I know the goal of reducing lattice basis it to get short and nearly orthogonal basis vectors, but why? what is the bigger picture?

To be fair, during past few months of reading papers, I found only few only sentences (here, and here):

Reduced bases allow to solve the following important lattice problems (SVP, CVP), either exactly or approximately

It would be greatly appreciated if I could get a direction or hint or something to help me figure out the concept.

$\endgroup$
4
$\begingroup$

Lattice Reductions in Lattice Crypto

Well to start off, lattice reductions are of interest in the context of lattice crypto because, as already stated in other answers, they allow us to find short vectors in a lattice, which relates to SVP (finding the shortest vector in a lattice).

We care about solving SVP because it is believed that there may be a security reduction from Ring Learning With Errors (RLWE) to SVP. So if we can solve SVP (via some technique e.g. lattice reduction) we may be able to break schemes based on RLWE e.g. these homomorphic encryption and key exchange schemes.

It should be noted that reduction techniques such as LLL do not allow us to solve SVP efficiently for lattices in a high dimension and as such they are not effective for breaking these schemes.

Lattice Reductions in Number Theoretic Crypto

But there's also an application to "classical" number theoretic crypto. I'll explain one (of several) possible applications. Suppose we want to attack (EC)DSA where nonces are generated with biased bits. It turns out we can use a lattice reduction to recover the private signing key.

If we can get enough message/signature pairs that all used nonces with the same bias then we can actually write a system of equations (with each equation corresponding to a message/signature pair) that can be interpreted as a lattice (just like how you can might use an augmented matrix in linear algebra to represent a system of equations).

We can then actually perform a lattice reduction (e.g. LLL) on this system of equations. If we have sufficient message/signature pairs then with high probability one of the entries in the reduced basis will be the private signing key. The details of this attack can be found in this paper.

For more information on lattice reductions in this context I'd encourage you to look at the paper Lattice Reduction: a Toolbox for the Cryptanalyst.

$\endgroup$
  • $\begingroup$ Just a (late) comment w.r.t. the terminology: I always hate it when someone uses "lattice reduction" instead of "lattice basis reduction". The basis is the object being reduced, not the lattice. The term "lattice reduction" suggests that the lattice somehow changes, which is clearly not the case. $\endgroup$ – TMM Feb 3 '17 at 19:05
1
$\begingroup$

It is much easier to determine the structure of the lattice when it is given by basis of short, nearly orthogonal vectors. For example, what does the set of lattice points in $$\Lambda = \mathbb{Z}(-3,4) + \mathbb{Z}(5,-7)$$ look like? What about $$\Lambda = \mathbb{Z}(1,0) + \mathbb{Z}(0,1)?$$

For both, it is $\mathbb{Z}^{2}$, but this was much easier to determine in the second case.

$\endgroup$
0
$\begingroup$

By studying lattice reduction algorithms, you may have the following applications in mind:

  1. For Cryptographic purposes: finding an approximate shortest vector of a lattice, which translates to see how efficiently you can solve SVP$_\gamma$. In fact, lattice reduction algorithms provide you with a trade-off between the complexity of solving SVP$_\gamma$ and $\gamma$ itself.
  2. For Coding Theory purposes: for example in a multiple-input multiple-output (MIMO) communication model, lattice reduction algorithms can be used as efficient precoders or MIMO receivers since theses algorithms help you improve the orthogonality defect of your bases. The more orthogonal the channel coefficients in this framework, the easier the error detection/correction.
$\endgroup$
  • $\begingroup$ This doesn't really answer the question. The OP was not asking about coding theory, and the point about cryptography is more or less a restatement of the question. $\endgroup$ – pg1989 Mar 30 '16 at 2:38
  • $\begingroup$ In particular, the LLL algorithm solves SVP$_\gamma$ for $n$-dimensional lattices, with $\gamma\leq 2^{(n−1)/2}$ in time $n^{O(1)}$. $\endgroup$ – Luckyluck63 Mar 30 '16 at 5:07
  • $\begingroup$ That fact along with some explanation of how/why would be a good answer to this question. If you edit I'll change my downvote to an upvote. $\endgroup$ – pg1989 Mar 30 '16 at 5:30
  • $\begingroup$ @Luckyluck63 you mentioned that: "In particular, the LLL algorithm solves SVP for n-dimensional lattices, with gamma < ...". Can you provide me with a paper or a resource so I can study this concept more in-depth? Essentially how gamma gets reduced. $\endgroup$ – Node.JS Mar 30 '16 at 5:36
  • 1
    $\begingroup$ @Node.JS to clarify this result, look at the Remark right after Proposition 1.12 in: cs.elte.hu/~lovasz/scans/lll.pdf and note that SVP$_\gamma$ means that you are looking for a vector ${\bf v}$ with $0\leq \|{\bf v}\|^2\leq d^2_{\min}(\Lambda)$ in an $n$-dimensional lattice $\Lambda$. $\endgroup$ – Luckyluck63 Mar 30 '16 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.