Score:4

What is the effect of low rank dual sublattices on the dual lattice attack on LWE?

ru flag

In the dual lattice attack of Espitau, Joux and Kharchenko (On a dual/hybrid approach to small secret LWE), the authors propose distinguishing (and subsequently recovering secret values) of LWE samples $(A,\mathbf b)=(A,A\mathbf s+\mathbf e)$ by finding dual vectors $(\mathbf x^T|\mathbf y^T)$ such that components of the vectors are small (with the possible exception of a small subset of components of $\mathbf y$) and $\mathbf x^TA=\mathbf y^T$. In this case if $\mathbf b$ is drawn from an LWE distribution $\mathbf x^T\mathbf b=\mathbf y^T\mathbf s+\mathbf x^T\mathbf e$ and the contribution to this expression from small components of $\mathbf x$ and $\mathbf y$ should itself on average, be small in comparison to the uniform $\mathbf b$ case. By finding many independent dual vectors, this should allow one to score samples $\mathbf b$ and exhaust over components of $\mathbf s$ to find small scoring values.

In the recent paper by the MATZOV group (Report on the security of LWE improved dual lattice attack) a number of variations on the EJK attack are considered that may have bearing on the security of the KYBER, SABER and DILITHIUM schemes inter alia. One of their proposals is in the generation of many short dual vectors in section 4 of their paper. They propose reducing components of the dual basis with the block-Korkine-Zolotarev (BKZ) method with block size $\beta_1$ and then using lattice "sieving" on reduced basis vectors to produce many short dual vectors. Their sieving method restricts itself to the first $\beta_2$ vectors in the BKZ basis and although they state that vectors can be produced from multiple reductions and sieves, in Remark 4.3 they observe that a single reduction and sieve seems optimal.

This means that all of the dual vectors that they use to produce their score lie in a rank $\beta_2$ sublattice of the dual space. Intuitively, one feels that if $\beta_2$ is small, then the contributions of the different vectors to the score will not be independent. This would be in violation of their assumption 4.4. Are there any theorems or heuristics as to how small a rank sublattice can be used in this way while still producing a score sufficiently powerful to distinguish/recover LWE samples/secrets?

sa flag
TMM
Maybe to ask a "simpler" question: is it obvious that if $\beta_2$ is, say, a smallish constant, the distinguisher is not as powerful anymore as when all vectors are drawn from the entire lattice?
Score:1
ru flag

This is not an answer.

In the hope of assisting anybody thinking about this and in light of @TMM's comment, here's a little bit more flesh around the statement "Intuitively, one feels that if $\beta_2$ is small, then the contributions of the different vectors to the score will not be independent".

Consider the case $\beta_2=1$. In this case all of our $(\mathbf x^T,\mathbf y^T)$ vectors will be multiples of a single generating vector, say $\alpha(\mathbf x_0^T,\mathbf y_0^T)$ with $\alpha$ perhaps some discrete Gaussian depending on the number of vectors. Now there are $q^{n-1}$ vectors $\mathbf v$ such that $\mathbf x_0^T\cdot\mathbf v=0$. Consider any vector of the form $\mathbf v+\mathbf e$ where $\mathbf e$ is drawn from the same distribution as the LWE sample. We expect perhaps $O(\sigma^nq^{n-1})$ such vectors (vectors with two such representations should be rare) and for large $n$ we might expect these to cover most of the space. The score of such vectors is given by $\alpha\mathbf x_0^T\mathbf e$ and the score of causal solutions is given by $\alpha(\mathbf x_0^T\mathbf e+\mathbf y_0^T\mathbf s)$. The space of causal vectors would be indistinguishable.

More generally for $\beta_2=k$ fixed, there would be a basis of $k$ $(\mathbf x_i^T,\mathbf y_i^T)$ vectors with our test set formed of linear combinations of basis vectors where the coefficients are Gaussian(?). Again there will be a set of $q^{n-k}$ vectors $\mathbf v$ perpendicular to all of the $\mathbf x_i^T$ and a perhaps a neighbourhood of $O(\sigma^nq^{n-k})$ of low scoring non-causal vectors.

This seems to suggest that $\beta_2$ should be at least $n\log \sigma/(\log q)$, but there could be other structural but non-causal sets as well as non-strucutural low scores. Likewise, the arguments for lack of overlap in the neighbourhood and between the causal sets are heuristic at best.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.