BGV参数设置
BGV参数设置
格知识基础（lattice）
格的定义
格（lattice）就是说在一个空间内，我定义一组basis向量（基向量）。然后这些basis向量加上整数系数构成的所有点就是格了。非常简单。最简单的例子就是我们的直角坐标系，（0，1），（1，0）就是basis向量，其它所有整数点都是格。画图就是：
我们再看详细的定义：
令$ v_1,..., v_n ^m$ 是一组线性独立向量.。格\(L\)是这些向量的线性组合所形成的空间。 \[ L = {a_1v_1 + a_2v_2 + ··· + a_nv_n : a_1, a_2,...,a_n} \in \mathbb{Z} \] 放在二维中就是坐标系中一系列的点：
最近向量问题(CVP)
定义 The Closest Vector Problem (CVP):给定一个向量\(w \in \mathbb{R}^m\)，这个向量不在格L中，我们需要找一个最短的向量\(v \in L\)，使得欧几里得范数(Euclidean norm)：\(\|v-w\|\)最小
如下图所示：
下面给出babai's Algorithm来解决最短向量问题：
- 把向量表示成如下形式（高斯消元法求解线性代数方程）：\(w = t_1v_1 + t_2v_2 + ··· + t_nv_n \;\; where \;\; t _1,...,t_n \in \mathbb{R}\)
- 令\(a_i = round(t_i) \in \mathbb{Z}\)，这里的round表示四舍五入取整
- 最后得到最短向量\(v = a_1v_1 + a_2v_2 + ··· + a_nv_n \;\; where \;\; a_1,...,a_n \in \mathbb{Z}\)
看起来很合理，但实际上对向量的基有要求，即这些基尽可能的正交，如果不正交，那么会得到错误的结果，如下图所示，这是一个二维的格，如果格的基夹角太小（正交的不好），那么会求得错误的结果
也就是说，我们有必要把格的基正交化
正交化
我们介绍几种正交化方法：
- 高斯算法，只能处理二维向量
- LLL格约算法，可以处理高维向量，让高维的基正交化
当维度很高的时候，正交化的时间复杂度较高，导致解密时间很长
LWE困难问题
LWE基本介绍
假设一个如下线性方程组： \[ \begin{equation} \left\{ \begin{array}{c} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=y_1 \\ a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=y_2 \\ \cdots \\ a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=y_n \end{array} \right. \end{equation} \]
要解这样一个方程很容易，只需要用高斯消元法可以一步步求解，但我们思考一个变式。如果把每一项都加上一个误差项呢？ $$ \[\begin{equation} \left\{ \begin{array}{c} a_{11}x_1+a_{12}x_2 + \varepsilon_2=y_2 \\ \end{array} \right. \end{equation}\] $$ 是不是这个问题就变得困难起来了，我们再仔细观察，很类似于CVP问题
在这个例子中\(\vec{v_i} =
(a_{i1},a_{i2},\dots,a_{in})\)为格中第\(i\)个基向量，而\((x_1,x_2,\dots,x_n)\)为我们要求解的系数，而\(\vec{w} =
(y_1,y_2,\dots,y_n)\)为随机向量。
RLWE介绍
原理与LEW类似，只不过把运算域搬到了多项式环上，其优点是：
- 加密的密钥更小
- 有了NTT优化多项式运算，加密时间更短
BGV参数设置
提出了一个经验推导的公式，该公式将给定密文模数大小logq的安全级别λ与维数n联系起来，从而推导安全性公式。
Lattices and Hermite Factor
给定一个矩阵\(B = (\vec{b_1},\vec{b_2},\dots,\vec{b_n})\)，以此作为基向量格的定义： \[ L = L(B) = \{\sum^k_{i=1}\gamma_i*\vec{b_i}:\gamma_i \in \mathbb{Z},\vec{b_i} \in B \} \]
假设有一个格\(L\)，那么他的体积表示为\(Vol(L) = \sqrt{det(B^TB)}\)
定义Hermite Factor: \[ \delta^k_0 = \|b_1\|/Vol(L)^{1/k} \] 这里的\(b_i\)为格L约简之后的基中的最短向量。
基于RLWE的安全方案
我们回顾LWE的方案：
密钥\(s\in \mathbb{Z}^n_q\),给定一个\(b\in \mathbb{Z}^m_q\)和\(A \in \mathbb{Z}^{m×n}_q\),满足\(A*s+e = b \mod{q}\)，这里e从误差分布中采样
基于LWE的方案的安全性取决于这个问题的难解性，而对这些方案的攻击是找到有效的算法来解决它们。有很多方案来解决LWE问题，其中大部分是基于格约简。也就是说，从一个差的格基，找到一个更好的，更正交的基。
实际中使用的最有名的格约简算法是BKZ(块Korkin-Zolotarev约简)。在这些算法中，时间复杂性和约化基的正交性由Hermite因子来表征。具体地说，算法的复杂度由Hermite因子来表示： \[ log(t_{BKZ}(\delta_o)) = \omega(- \frac{log(log(\delta_0))}{log(\delta_0)}) \]
BGV安全性分析
我们考虑满秩的格L，格的最短向量的范数为\(\|\vec{b_1}\| = \delta^kq^{n/k}\),攻击者选择一个采样数M，使得\(\|b_1\| = \delta^Mq^{n/M}\)
最小，前几年的工作表明，当\(M = \sqrt{nlog(q)/log \delta_0}\)的时候，可以缩减最短向量\(\|\vec{b_1}\| = q\)，这表明 \[ log q = log(\delta_0^M q^{n/M}) = 2\sqrt{nlog(q)log(\delta_0)} \\ \Rightarrow n = log(q)/(4log(\delta_0)) \] 我们把这个等式代入到，等式(6)，可以得到对应的BGV参数设置 \[ \lambda \approx -log(\cfrac{A*log(q)}{n})\cfrac{Bn}{logq} + C\sqrt{\cfrac{logq}{n}}log(\cfrac{n}{log(q)}) \] 其中\(\lambda\)为安全参数，\(log(q)\)为密文模数的比特数
当错误分布为高斯分布的时候:
- A = 0.65
- B = 0.53
- C = 22.88
