0
$\begingroup$

In the Kyber Algorithm specifications document, chapter 5.1.2 primal attack, it says that:

Given the matrix LWE instance $(A,b=As+e)$, one builds the lattice $\Lambda = \{x\in \mathbb{Z}^{m+kn+1}:(A\vert I_m\vert -b)x=0 \,mod \,q\}$ of dimension $d=m+kn+1$, volume $q^m$, and with a unique-SVP solution $v=(s,e,1)$ of norm $\lambda\approx\varsigma\sqrt{kn+m}$, where $\varsigma$ is the standard deviation of the individual secret/error coefficients.

To my mind, $\Lambda = q\,L(A\vert I_m\vert -b)^{\lor}$, where $L^{\lor}$ represent the dual of lattice $L$.and $L(A\vert I_m\vert -b)^{\lor}=L(b_1, \dots, b_{m})$, where $b_i$ is the column vector with $b_i^{(j)}$ represtion its j-th component(start from 0), satisfy $$b_i^{(nk+i-1)}=1, b_i^{(nk+j)}=0, j\ne i-1, i=1, \dots, m.$$ So $\Lambda =L(q\,b_1,\dots,q\,b_{m})$...

Is that correct?

If it is right, then how can $v=(s,e,1)$ be linearly represented by $q\,b_1,\dots,q\,b_{m}$?

If this is not right, how can I figure out

What is the basis of $\Lambda$ ?

and

Why is the volume $q^m$?

Or, are there any references?

$\endgroup$
1
  • $\begingroup$ Since $L(A\vert I_m\vert -b)\subset L(I_{kn + m + 1})$, by corollary 2.7 (2) in the different ideal, that is $L_1 \subset L_2 \Longleftrightarrow L_2^\lor \subset L_1^\lor$, so I can sure $L(A\vert I_m\vert -b)^\lor \supset L(I_{kn + m + 1})^\lor = L(I_{kn + m + 1})$ $\endgroup$
    – qiuxicj
    Commented Oct 27, 2023 at 2:04

1 Answer 1

0
$\begingroup$

Whereas it is true that each of the $b_i$ vectors lies in the dual to the lattice generated by the rows of $A|I_m|b$, there are vectors in the dual that do not lie in the span of the $b_i$. For instance, let $\mathbf w\in \mathbb Z^{kn}$ be any vector in the row span of $A^{-1}$ then $(\mathbf w|0|0)$ is also in the dual. Likewise the vector $\frac1q(s,e,1)$ lies in the dual, but not in the span of the $b_i$.

$\endgroup$
1
  • $\begingroup$ Thanks for your help! You are right. But how can I figure out the basis of $\Lambda$ and why is the volume $q^m$. Since $ L(A\vert I_m\vert -b)\subset L(I_{kn + m + 1})$, by corollary 2.7 (2) in the different ideal, that is $L_1 \subset L_2 \Longleftrightarrow L_2^\lor \subset L_1^\lor$, so I can sure $L(A\vert I_m\vert -b)^\lor \supset L(I_{kn + m + 1})^\lor = L(I_{kn + m + 1})$. $\endgroup$
    – qiuxicj
    Commented Oct 27, 2023 at 2:15

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.