同态加密GSW方案学习笔记1-GSW最初方案概述

大家好，我是讯享网，很高兴认识大家。

概述

同态加密和 LWE 问题不再赘述。
Conceptually-Simpler：从概念上更加简单。因为在 GSW 方案中所使用的的密文都是矩阵。因此在进行同态运算加或乘的时候，只需将矩阵进行加或乘即可。在这之前，同态加密运算乘法非常复杂。
Asymptotically-Faster：渐进更快。在理论上每次乘法的计算量为 $n^{\omega}$ ，其中 $\omega < 2.3727$ 是矩阵乘法常数。以往的方案中重线性化都需要 $n^3$ 的计算量。
First identity-based FHE scheme：本文提出了第一个基于身份的 FHE 方案，即相同身份 (ID) 下的密文可以进行同态运算。
First attribute-based FHE scheme：本文提出了第一个基于属性的 FHE 方案，即相同属性下的密文可以进行同态运算。

此外，由于该方案是基于 BGV 方案设计的同态加密方案，因此从 BGV 方案中继承了许多优点：

这是一个不需要自举的层次同态（多项式层）
没有模转换 (modulus switching)
安全性保障：
- Based on classical GapSVP (基于经典 GapSVP)
- 如果使用自举：Based on LWE for quasi-polynomial factors (基于拟多项式参数的 LWE)

GSW 方案整体思想：近似特征向量技术

基础设置

首先假设我们有这样的一个设置：一个矩阵 ${\color{blue}C}$ 乘以 ${\color{green}v}$ 等于一个特征值乘以 ${\color{green}v}$ ， ${\color{green}v}$ 是这个矩阵的特征向量，这里的 ${\color{red}\mu}$ 是特征值：
GSW近似特征向量整体思想1
讯享网
现在想象一下，把 ${\color{blue}C}$ 看作密文， ${\color{green}v}$ 看作密钥，要加密的消息是 ${\color{red}\mu}$ ：
GSW近似特征向量整体思想2
很容易可以发现这个形式具有同态的性质：密文的加或乘相当于明文的加或者乘。即假设 ${\color{blue}C_1} \sdot {\color{green}v} = \mu_1 \sdot {\color{green}v}$ mod $q$ ，并且 ${\color{blue}C_2} \sdot {\color{green}v} = \mu_2 \sdot {\color{green}v}$ mod $q$ ，则 ${\color{blue}C_1} \sdot {\color{blue}C_2} \sdot {\color{green}v} = \mu_1 \sdot \mu_2 \sdot {\color{green}v}$ mod $q$

然而，这个形式虽然具有同态的性质，但是很明显非常的不安全，因为找到一个矩阵的特征向量很简单，密钥很容易得到。为了保证安全性，我们可以将其转换为 LWE 的形式：
GSW近似特征向量整体思想3

$e$ 是系数很小的噪声向量 (<<q)
${\color{green}v}$ 是一个近似特征向量 (approximate eigenvector)

方案的同态性质

现在我们来看看同态的性质是否还在：
GSW近似特征向量整体思想4
发现同态加和乘仍然成立，但是乘法中有新的噪声项。

方案的噪声处理

为了让这个噪声项尽量小，我们对这个新的噪声进行分析：

可以减小 ${\color{red}\mu_2}$ ，即让消息空间变小。要达到这个目的仅需将消息空间设置成 ${0, 1\}$ 即可。GSW 方案中使用与非门 (NAND gats) 可将消息空间设置成 ${0, 1\}$ 。
可以使密文 ${\color{blue}C}$ 变小。密文可能是两个密文的乘法，即使初始的密文很小，计算后也可能得到较大的密文。是否能有什么技术能够使得密文一直保持在很小的范围内（甚至在 {0, 1} 内）？文中提出一种 Flatten ciphertext 的技术。

如果我们能够限制密文的大小：

同态乘法会将噪声扩大至多 $n + 1$ 倍（全部代入 1 可得）
在噪声达到 $q$ 之前可以评估深度为 $\Theta(log_{n + 1} q)$ 的电路
令 $q$ 足够大，例如令 $^{n^{\Theta(1)}}$ ，则我们可以评估多项式深度，并且得到一个层次全同态方案。

限制密文大小

那么我们怎么限制密文的大小？这里需要使用分解技术。

首先先定义一些符号：

$\pmb{a} \in \mathbb{Z}_q^k$ 其中 $k$ 是维度， $q$ 是模。
$\lfloor log_q \rfloor + 1$ 是 $q$ 的对数
$\sdot l$

定义一些函数：

$BitDecomp(\pmb{a}) = (a_{1, 0}, ..., a_{1, l-1}, ..., a_{k, 0}, ..., a_{k, l-1})$ 是 $\pmb{a}$ 的每个系数的比特分解，从最低位到最高位 (least to most significant)。
$BitDecomp^{-1}(\pmb{b} \in \mathbb{Z}_q^N) = (\sum_j 2^j b_{1, j}\; mod \; q, ..., \sum_j 2^j b_{k, j} \; mod \; q)$ 是上面那个比特分解函数的逆函数。
$Flatten(\pmb{b} \in \mathbb{Z}_q^N) = BitDecomp(BitDecomp^{-1} (\pmb{b}))$ 是一个系数都在 ${0, 1\}$ 中的向量。
$Powersof2(s) = (s_1, 2s_1, ..., 2^{l - 1}s_1, ..., s_k, 2s_k, ..., 2^{l -1}s_k) \; mod \; q$

有一些显而易见的结论：

对于任意 $\pmb{a}, \pmb{s} \in \mathbb{Z}_q^k$ ，有 $<\pmb{a}, \pmb{s}> = <BitDecomp(\pmb{a}), Powersof2(\pmb{s})>$
对于任意 $\pmb{b} \in \mathbb{Z}_q^N$ 和 $\pmb{s} \in \mathbb{Z}_q^k$ ，有 $<\pmb{b}, Powersof2(\pmb{s})> = <BitDecomp^{-1}(\pmb{b}), \pmb{s}> = <Flatten(\pmb{b}), Powersof2(\pmb{s})>$

这些函数和结论如何在同态加密方案中应用呢？

现在我们给出近似特征向量的一个特殊形式：

${\color{green}v} = Powersof2(s)$ 其中 $s$ 是随机的

开始 Flatten Ciphertext （展平密文）：

假设对于一个与非门（NAND）： ${\color{blue}C^{NAND}} = I_N - {\color{blue}C_1} \sdot {\color{blue}C_2} \; mod \; q$
令 ${\color{blue}C_3} \leftarrow Flatten({\color{blue}C^{NAND}})$ 为 ${\color{blue}C^{NAND}}$ 每一行的展平结果， ${\color{blue}C_3}$ 中所有的系数都在集合 ${0, 1\}$ 中。
则 ${\color{blue}C_3} \sdot {\color{green}v} = {\color{blue}C^{NAND}} \sdot {\color{green}v} \; mod \; q$ ，我们没有改变加密的消息，甚至没有增加噪声。

现在，我们拥有了一个层次全同态。

GSW 基本加密方案

设置 $Setup(1^n, 1^L)$ ：选择一个 $k(\lambda, L)$ bit 的模 $q$ ，格的维度参数是 $n(\lambda, L)$ ，适当地为 LWE 取误差分布 $X(\lambda, L)$ 使得在已知攻击下达到 $2^{\lambda}$ 的安全性。同时，选择参数 $m(\lambda, L) = O(n log \, q)$ 。令参数集 $p a r a m s = (n, q, X, m)$ ，令 $\lfloor log _q \rfloor + 1, N = (n + 1) \sdot l$ 。
密钥生成 $S e c r e t K e y G e n (p a r a m s)$ ：采样 $\vec{t} \leftarrow \mathbb{Z}_q^n$ ，输出 $\vec{s} \leftarrow (1, -t_1, ..., -t_n) \in \mathbb{Z}_q^{n + 1}$ 。令 $\leftarrow Powersof2(s) \in \mathbb{Z}_q^N$
公钥生成 $P u b l i c K e y G e n (p a r a m s, s k)$ ：均匀生成一个矩阵 $\leftarrow \mathbb{Z}_q^{m \times n}$ 和一个向量 $\vec{e} \leftarrow \chi^m$ ，设 $\vec{b} = B \sdot \vec{t} + \vec{e}$ ，设 $A$ 为 $(n + 1)$ -列矩阵，由 $\vec{b}$ 和 $B$ 的 $n$ 列组成。设置公钥为 $p k = A$ （注意：观察到 $\sdot \vec{s} = \vec{e}$ ），这里公钥看作一个LWE实例，是由向量组成的矩阵，且与密钥点积得到的结果很小。
加密 $\mu)$ ：为了加密消息 $\mu \in \mathbb{Z}_q$ ，均匀采样一个矩阵 $\in \{ 0, 1 \}^{N \times m}$ ，可得 $\sdot R$ 的每一行为 $0$ 的加密，因为他们与密钥的点积的结果非常小。同时输出如下的密文 $C$ ： $Flatten(\mu \sdot I_N + BitDecomp(R \sdot A)) \in \mathbb{Z}_q^{N \times N}$
解密 $D e c (C, v)$ ：计算 $\sdot v = \mu \sdot v + Bitdesomp(\pmb{R} \sdot \pmb{A}) \sdot v = \mu \sdot v + \pmb{R} \sdot \pmb{A} \sdot \pmb{s} = \mu \sdot v + small$ ，从 $2^{l - 1} + small$ 中获得明文 $\mu$ 。
同态操作：在密文上进行加法/乘法后，展平密文。

参考资料

参考论文：Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2013: 75-92.
参考论文：Alperin-Sheriff, Jacob, and Chris Peikert. “Faster bootstrapping with polynomial error.” Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2014.
参考视频：https://www.youtube.com/watch?v=uabmoq4-tGQ
参考视频：https://www.youtube.com/watch?v=tczcle2T-Ak
参考 PPT ：http://yuyu.hk/files/FHE.pdf
参考文章：https://blog.csdn.net/Artisgrammer/article/details/
参考文章：https://blog.csdn.net/yuxinqingge/article/details/