What is a purpose of reducing lattice basis?

Question

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 its 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 is 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 there):

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.