RLWE转化为CVP

1. RLWE问题中的方案:

$$t(X)\equiv a(X)\cdot s(X)+e(X)(modp)$$

2. 相应的矩阵形式为:

$$t^{\ast }\equiv M(a)s^{\ast }+e^{\ast }(modp)$$

3. 存在整向量$s^{ex}=(\begin{array}{c}{s}^{\ast }\\ r\end{array})\in {\mathbb{Z}}^{2n}$，$\mathrm{\Lambda }$中格点$M(a{)}^{ex}\cdot s^{ex}$与目标向量$t^{ex}$的差向量为：

$$t^{ex}-M(a{)}^{ex}\cdot s^{ex}=\left(\begin{array}{c}{e}^{\ast }\\ s^{\ast }\end{array}\right)$$

4. 如果条件RLWE问题中的$s(x)$要求是短多项式，则可以构造2n阶整方阵:

$$M(a{)}^{ex}=\left(\begin{array}{cc}M(a)& q{I}_n\\ -I_n& 0\end{array}\right)\in {\mathbb{Z}}^{2n\times 2n}$$

• 其中$l_n$是$n$阶单位矩阵,$q{l}_n$是$l_n$的$q$倍
  

5. 设$\mathrm{\Lambda }$是$M(a{)}^{ex}$列张成的格，定义目标（列）向量：

$$t^{ex}=\left(\begin{array}{c}{t}^{\ast }\\ 0\end{array}\right)$$

6. 存在整向量$s^{ex}=\left(\begin{array}{c}{s}^{\ast }\\ r\end{array}\right)\in {\mathbb{Z}}^{2n}$, $\mathrm{\Lambda }$中格点$M(a{)}^{ex}{s}^{ex}$与目标向量$t^{ex}$的差向量为

$$t^{ex}-M(a{)}^{ex}{s}^{ex}=\left(\begin{array}{c}{e}^{\ast }\\ s^{\ast }\end{array}\right)\in {\mathbb{Z}}^{2n}$$

7. 由于$e$和$s$都是选取比较短的多项式，$\left(\begin{array}{c}{e}^{\ast }\\ s^{\ast }\end{array}\right)$是较短的整向量

8. 故RLWE问题就转化为格$\mathrm{\Lambda }$中的CVP求解

$$\left(\begin{array}{c}p\\ & p\\ & & p\\ & & & \cdots \\ & & & & p\\ a_0& a_1& a_2& \cdots & a_{n-1}& 1\\ -2024a_{n-1}& a_0& a_1& \cdots & a_{n-2}& & 1\\ -2024a_{n-2}& -2024a_{n-1}& a_0& \cdots & a_{n-3}& & & 1\\ ⋮& ⋮& ⋮& \ddots & ⋮& & & & \cdots \\ -2024a_1& -2024a_2& -2024a_3& \cdots & a_0& & & & & 1\\ b_0& b_1& b_2& \cdots & b_{n-1}& & & & & & 1\end{array}\right)$$$$(k_0,k_1,k_2,...k_{63},s_0,s_1,s_2,...s_{63},1)\left(\begin{array}{c}p\\ & p\\ & & p\\ & & & \cdots \\ & & & & p\\ a_0& a_1& a_2& \cdots & a_{n-1}& 1\\ -2024a_{n-1}& a_0& a_1& \cdots & a_{n-2}& & 1\\ -2024a_{n-2}& -2024a_{n-1}& a_0& \cdots & a_{n-3}& & & 1\\ ⋮& ⋮& ⋮& \ddots & ⋮& & & & \cdots \\ -2024a_1& -2024a_2& -2024a_3& \cdots & a_0& & & & & 1\\ b_0& b_1& b_2& \cdots & b_{n-1}& & & & & & 1\end{array}\right)=(e_0,e_1,e_2,...e_{63},s_0,s_1,s_2,...s_{63},1)$$