How can BDD solve LWE if the matrix A is full rank?

Sam Jaques

6/8/23, 11:43 AM

I'm trying to figure out exactly how solving different generic lattice problems can solve LWE, and in particular, BDD. Everything I've found says that since an LWE sample is $(A,b=As+e\mod q$), then the lattice $L_q(A)=\{v : \exists x:Ax=v\mod q\}$ contains $As$, so $b$ is within distance $\Vert e\Vert$ of that lattice. Hence, if a BDD solver can solve for distances up to $\Vert e\Vert $, on input $b$ it should return $As$.

However, if $A$ is an $n\times n$ matrix (such as in Frodo), then with high probability $A$ has full rank over $\mathbb{F}_q$. Thus means all vectors in $\mathbb{F}_q^n$ are in the span of $A$, so $L_q(A)=\mathbb{Z}^n$. Then, since $e$ is also an integer vector, $b\in L_q(A)$, so BDD is useless: on input of $b$, it would return $b$.

Can BDD solve LWE here? Is an approximate SVP solver more natural?

0 + 0

lattice-crypto

Chris Peikert

6/9/23, 1:01 AM

For Frodo and others like it, the coefficient vector $x$ of the lattice point is “short,” so $Ax$ does not cover all of $\mathbb{Z}_q^n$. See the FrodoKEM submission’s modeling of this “normal form” LWE as a BDD problem for a suitable setup of a lattice and nearby BDD vector.

Sam Jaques

6/9/23, 10:24 AM

The FrodoKEM submission explains how BDDwDGS reduces to LWE, then gives attacks based on uSVP, but I can't find an attack based on BDD directly (i.e., a reduction from LWE to BDD). I found a reduction from uSVP to BDD, so one could do LWE=>uSVP=>BDD, but is that all?

Chris Peikert

6/9/23, 10:34 AM

Section 5.2.2 has the reduction LWE<=uSVP. See also Section 5.2.3.

Sam Jaques

6/9/23, 10:41 AM

I saw that and I was chewing through the details (my last comment probably has => backwards). So uSVP can solve normal form LWE fairly directly, but BDD needs to "go through" uSVP first in order to solve LWE?

Chris Peikert

6/9/23, 11:51 AM

Not sure what you mean by “BDD needs to…” LWE is just an average-case BDD problem. Note that Sec 5.2.3 covers an LWE/BDD attack that doesn’t go through uSVP.

Sam Jaques

6/9/23, 1:36 PM

My original question is how to see LWE as an average-case BDD problem, given that the natural lattice to use ($L_q(A)$) contains the LWE sample $b$. Sec 5.2.3 seems to use short lattice vectors directly -- the $(v,w)\in \hat{\Lambda}$. My specific question is: If I have a BDD solver, and a normal form LWE sample $(A,b=As+e)$, what lattice $L$ and what close vector $t$ do I give to the BDD solver?

Chris Peikert

6/9/23, 2:12 PM

Ok. The relevant lattice is the “$q$-ary parity-check lattice” of integer vectors $z$ such that $[A \mid I]z = 0 \pmod{q}$. The target $b = As + e = [A \mid I] (s,e)$ is a “syndrome” that specifies the lattice coset obtained by slightly shifting the lattice, by the short vector $(s,e)$. (This is an equivalent conception of the BDD problem: given a lattice and a coset obtained by a small shift, find that shift.) A good exercise is to write down an explicit basis for this lattice, and to convert $b$ into an explicit BDD target vector in the ambient space of the lattice.

Sam Jaques

6/9/23, 6:11 PM

Oh excellent! That's exactly what I was asking about, thanks.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How can BDD solve LWE if the matrix A is full rank?

TH: BDD จะแก้ LWE ได้อย่างไรหากเมทริกซ์ A เต็มอันดับ

RO: Cum poate BDD să rezolve LWE dacă matricea A este de rang complet?

RU: Как BDD может решить LWE, если матрица A имеет полный ранг?

VI: Làm cách nào BDD có thể giải quyết LWE nếu ma trận A có thứ hạng đầy đủ?

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.