LWE的利用sparsification的嵌入

LWE的Sparsified Embedding 的描述与Performance

前文介绍过LWE的Kannan Embedding (虽然实际上似乎并没有介绍). Kannan Embedding和后文的Bai and Galbraith’s embedding 实际上都是将BDD格嵌入一个大格, 构造uSVP问题对他进行一个解决的方法. 本质上其实是$BDD_{\alpha}\longrightarrow uSVP_{\gamma}$的格嵌入.

如果这个格能变得稀疏一点就好了啊—— 大概可能有人会这么想. 稀疏的格有很多好处, 最经典的就是determinant变大了, 如果最短向量不发生改变或者改变不是很大的话, 在这个格中求解$uSVP$问题的时候, $\gamma$值将会变得更大. 而$\gamma$​​的变大将会明显的减少2016 estimate描述的BKZ求出最短向量的block的大小. 这便是sparsified embedding的思路. Sparsified Embedding 方法先对BDD格稀疏化, 然后将它嵌入到一个SVP格中.

嵌入描述

1. step 1: Sparsifying 这一步的的目的就是为了稀疏化BDD格. 令原有的BDD格为

   $$\Lambda_{(\bold{A},q)}=\left\{\bold{v}\in\mathbb{Z}_{q}^{m}\ |\ \bold{b}\equiv\bold{Ax}\pmod{q} \text{ for some }\bold{x}\in\mathbb{Z}^{n}\right\}$$

   考虑一个公共参数$p$, 这个参数描述的就是将$\Lambda_{(\bold{A},q)}$稀疏化的倍数.​B 为格$\Lambda_{(\bold{A},q)}$的一组格基.

   1. $\bold{z},\bold{u}\stackrel{$}{\longleftarrow}\mathbb{Z}^{m}_{p}$​, 独立选取嗷.

   2. $\bold{w}=\bold{Bu}$

   3. check下述条件. 如果满足, 则继续进行. 否则重新开始. 其中参数$l_0$的选取来自另一篇文章, 本文不多做展开:

      $$\left\|\bold{b}+\bold{w}\right\|<\frac{(m+1)l_0}{\sqrt{2}}$$