How to determine the concrete security of lattice cryptosystems?

Question

I am currently reading about lattice cryptography and am interested in the cryptosystems based on the LWE problem. I understand the reductions from lattice problems to dLWE. Then we base our belief in the cryptosystem (say Regev or dual Regev PKC) on dLWE. But this is however asymptotic. From what I understand, the way this works is we believe breaking SIVP or whatever lattice problem takes time a very large function of n, and from the reduction we get a SIVP solver, so any algorithm which breaks the cryptosystem also is necessarily is a very large function of n.

What I don't understand however is how does one give parameters to these cryptosystems (for example, if I want 128 bits of security, how large should the LWE instance be)? I have read a couple of papers on this topic and have not really understood it. My comprehension is that we solve LWE like an instance of BDD. But these papers discuss basis reduction and ways of solving SVP and I do not know how to link these things together.

Sorry, my English is really bad.

Answer 1

Depending on whether your lattice-based cryptosystem has security reduction or not, there exists two types of parameters:

$\textbf{1. Provably secure:}$ For a cryptosystem with provable security, the parameters are chosen according to the underlying reduction. For example, suppose your cryptosystem is based on the hardness of LWE problem. Now, assuming that the desired security level $\ell$ is identical to the hardness level of the LWE problem (i.e., without involving the gap induced by the security reduction), one can determines the best known solver $D$ for the LWE problem and ensures that its corresponding parameters offer a hardness of $\ell$ bits. In order to find also the best known solver for LWE and measure the bit hardness of LWE instances, the estimator by Albrecht et al. [APS15] can be used.

$\textbf{2. Non-provably secure:}$ If the cryptosystem is not provably secure, then identify the best known attack $A$ on the cryptosystem and select parameters satisfying $\frac{t_A}{\varepsilon_A} \geq 2^{\ell}$, where $t_A$ and $\varepsilon_A$ are the running time and success probability of $A$, respectively.

See this paper for more details.

Answer 2

While the reduction from hard lattice problems to LWE provides evidence for its qualitative hardness, it does not say much about it quantitative hardness because it is not very tight. So for cryptanalysis it is usually conjectured that LWE is hard and in order to estimate its concrete hardness one looks at all possible algorithm that solve LWE (among others, there are lattice algorithms that solve BDD as you mentioned). To get a good overview of these algorithms and the concrete hardness of LWE, I recommend reading this.

Hope that helps.