4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Parameters are always chosen based on best known attacks. If you use the LWE problem as the underlying hard problem, and e.g. you use the provable reduction from LWE to SIVP, then still you'd somehow have to estimate the hardness of SIVP. And a reduction does not mean it is probably secure - it just means that you cannot break the scheme significantly faster than solving the underlying hard problem. (This problem may still be easy.) $\endgroup$ – TMM Jul 11 '17 at 2:23
2
$\begingroup$

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.

$\endgroup$

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.