3
$\begingroup$

What's actually the difference between a (noisy) CVP and LWE? It seems to me that both are the same.

With the definition of LWE: $$A * s + e = b$$

solving for secret vector s is the same than solving for the coefficients of the CVP, or do i understand something completely wrong?

$\endgroup$

2 Answers 2

3
$\begingroup$

In learning with errors the solution vector $\mathbf s$ and rows of $A$ are taken to lie in a finite ring $\mathbb Z_q^n$. The solution is not necessarily unique as multiple $\mathbf s$ and $\mathbf e$ might be obtainable from the specified distribution, but with different likelihoods. The causal solution is not necessarily the most likely for given set of samples $A$. Note that it is also possible to have an LWE problem with more than $n$ samples, which usually leads to degeneracy in the CVP case.

For a generic close vector problem the solution "$\mathbf s$" is allowed to lie in the infinite space $\mathbb Z^n$ and the basis elements "the rows of $A$" are allowed to lie in an ambient vector space such as $\mathbb R^n$. There is typically a unique closest solution barring pathological cases where the target vector is equidistant from two lattice vectors.

LWE variations may place more constraints on the structure of $\mathbf s$, $\mathbf e$ and the rows of $A$.

LWE instances can be turned into instances of CVP (if necessary by augmenting with entries of the $qI$ form) but the closest vector is not guaranteed to be the causal answer.

$\endgroup$
3
  • $\begingroup$ Looked at the given links. Didn't see a definition of "causal solution". $\endgroup$
    – kodlu
    Jan 13 at 20:55
  • $\begingroup$ Well, arguably the generation of the problem is another difference. In CVP $\mathbf b$ is unpspecified as to its construction. In LWE $\mathbf b$ is constructed by sampling $A$ and $\mathbf e$ for a given $\mathbf s$. It is this $\mathbf s$ and its corresponding $\mathbf e$ that I refer to as "causal". This does not preclude the existence of $\mathbf s'$ and $\mathbf e'$ for which the vector $\mathbf b$ is more likely. $\endgroup$
    – Daniel S
    Jan 13 at 21:19
  • $\begingroup$ Thanks a lot for your answer! it's clear now. $\endgroup$
    – lstk44
    Jan 17 at 9:11
1
$\begingroup$

CVP is also a worst-case problem, LWE is an average-case problem. The particular average-case distribution that LWE focuses on has an explicit name ("construction A lattices applied to random $q$-ary codes"), but is not only average-case distribution of lattices. In fact, for arbitrary lattices in $\mathbb{R}^n$, there is a more natural distribution of lattices (typically called the "Siegal measure" $\mu_n$), where one gets formula such as $\int_{\mu_n} f(L)d\mu_n = \int_{\mathbb{R}^n} f(x)dx$, e.g. one can relate the average value of a function on a lattice $f(L) = \sum_{x\in L\setminus\{0\}} f(x)$ to a standard integral of that function. This precise identity is usually called an "integration formula". Specific examples are Siegal's integration formula and Rodger's integration formula.

Iirc for large-enough parameters (not used in crypto) the LWE lattice distribution does approach the Siegal measure, so in an asymptotic sense this is not new information, but as we do crypto the distributions are concretely different.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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