GSW 近似特征向量同态加密

形式陈述

GSW 构造的核心关系是

Cv=\mu v+e\pmod q. \tag{1}

$C$ 是公开密文矩阵， $v$ 是秘密向量，消息 $\mu$ 是近似特征值， $e$ 是受控的小误差。普通矩阵乘法因而能对应明文乘法。[1] 要把这句话变成安全的同态加密，还需规定 $C,v$ 的特殊形状。

取正整数 $n,m$ 与模数 $q\ge3$ ，令 $\ell=\lfloor\log_2q\rfloor+1$ 、 $N=(n+1)\ell$ 。对 $a\in\mathbb Z_q^{n+1}$ ， $\operatorname{BD}(a)$ 把每个坐标的标准代表分解成 $\ell$ 个低位在前的二进制位。定义

\operatorname{P2}(s)=(s_0,2s_0,\ldots,2^{\ell-1}s_0;\ldots;s_n,\ldots,2^{\ell-1}s_n).

$\operatorname{BD}^{-1}$ 将每个长度 $\ell$ 的块按权重 $1,2,\ldots,2^{\ell-1}$ 加回，再模 $q$ ；输入块无须已经是二进制。令

\operatorname{Flatten}(w)=\operatorname{BD}(\operatorname{BD}^{-1}(w)).

对矩阵逐行应用这些操作。它们满足

\operatorname{BD}(a)\cdot\operatorname{P2}(s)=a\cdot s, \qquad \operatorname{Flatten}(w)\cdot\operatorname{P2}(s)=w\cdot\operatorname{P2}(s) \pmod q. \tag{2}

密钥、加密与一位解密

取均匀 $t\in\mathbb Z_q^n$ 、 $B\in\mathbb Z_q^{m\times n}$ ，独立抽误差 $e_0\leftarrow\chi^m$ ，令

b=Bt+e_0,\quad A=(b\mid B),\quad s=(1,-t),\quad v=\operatorname{P2}(s).

公开 $A$ ，保留 $s$ ，于是 $As=e_0\pmod q$ 。加密一位 $\mu$ 时均匀抽 $R\in\{0,1\}^{N\times m}$ ，输出

C=\operatorname{Flatten}\bigl(\mu I_N+\operatorname{BD}(RA)\bigr).

$C$ 为 $N\times N$ 二进制矩阵，并有 $Cv=\mu v+Re_0$ 。在 $v$ 的第一块选一个已知坐标 $v_j=2^j\in(q/4,q/2]$ ，计算 $(Cv)_j$ ，按模 $q$ 圆周距离选择更接近0还是 $v_j$ 。若误差各坐标的绝对值都小于 $q/8$ ，这个解密正确。

安全性假设是所选参数的均匀秘密判定LWE困难性；还要让 $m$ 留足随机子集和熵余量。例如若每行统计误差上界为 $\eta_0=\frac12\sqrt{q^{n+1}/2^m}$ ，应使 $N\eta_0$ 可忽略。正确性则要求噪声预算与所支持深度相容。这些是同时要满足的条件。

直觉

若没有误差， $v$ 就是每份密文共同的特征向量，消息就是相应特征值。两个矩阵相乘时，特征值相乘，这是同态运算的代数来源。

真正困难的是误差。普通矩阵经过多轮乘法后，系数很快变大，接下来会把另一份密文的误差放大。gadget 表示允许每次把大系数重新写成位，而不改变矩阵作用于秘密 $v$ 的结果。服务器不知道 $v$ ，仍可完成这种“改写表示”。

两份密文作用于同一秘密向量；乘法误差分成C1乘e2与消息μ2乘e1，Flatten只压小矩阵系数而不消除既有误差。

例子与边界

三个位怎样保住一个内积

取 $q=7,\ell=3$ ， $a=(5,3)$ 、 $s=(2,1)$ 。低位在前的分解为

\operatorname{BD}(a)=(1,0,1;1,1,0),\qquad \operatorname{P2}(s)=(2,4,1;1,2,4)\pmod7.

展开后的内积为 $2+1+1+2=6$ ，原内积为 $5\cdot2+3\cdot1=13\equiv6\pmod7$ 。这些位不是把秘密公开拆开；公开的是密文坐标的位，秘密向量的重复倍数只由持钥者计算。

再取一个不是二进制的块 $w=(3,2,0)$ 。压回去得到 $3+2\cdot2=7\equiv0$ ，再展开为 $(0,0,0)$ 。它们与 $(s,2s,4s)$ 的内积都模7等于零。这说明 Flatten 可以把系数从3、2改为0、0，同时保持式 (2)。

一个NAND门的完整误差账本

设 $C_i v=\mu_i v+e_i$ ，其中 $\mu_i\in\{0,1\}$ 。先乘：

C_1C_2v =C_1(\mu_2v+e_2) =\mu_1\mu_2v+\mu_2e_1+C_1e_2.

所以 NAND 可定义为

C_{\mathrm{NAND}}=\operatorname{Flatten}(I_N-C_1C_2).

新消息为 $1-\mu_1\mu_2$ ，新误差为 $-(\mu_2e_1+C_1e_2)$ 。因为进入每一门的 $C_1$ 已经 Flatten，系数都是0或1，用无穷范数与行和界可得

\|e_{\mathrm{out}}\|_\infty \le\|e_1\|_\infty+N\|e_2\|_\infty.

若两输入都以 $E$ 为界，则下一层以 $(N+1)E$ 为界。对深度至多 $L$ 的 NAND 电路，保守充分条件为

(N+1)^L E_0<q/8,\qquad E_0\ge\|Re_0\|_\infty. \tag{3}

NAND 是通用门，因此这一账本覆盖通用 Boolean 计算。若直接把加法当 XOR，却仍把中间消息当作0或1，误差分析就会用错：模 $q$ 的 $1+1$ 是2，不是0。

例如只检查算术预算，取 $q=65537,n=1$ ，则 $\ell=17,N=34$ 。假设新鲜误差界 $E_0=1$ ，逐层上界为1、35、1225、42875。前两层小于 $q/8=8192.125$ ，第三层的这一充分证书失效。失去上界证书不表示每个具体密文必然解错；也不表示这些微小维数参数安全。

Flatten没有洗掉噪声

式 (2) 保持 $Cv$ ，所以它也保持已有误差。它修复的是下一步误差将被多大系数放大的问题，而非把已经增长的误差降回新鲜水平。

如果省去 Flatten，下一次左乘矩阵的行和可能接近 $Nq$ ，式 (3) 就不再成立。这是位分解在构造中的必要作用，不是为了让文件看起来更像二进制。

推论与应用

安全证明用两段混合。先以 LWE 把 $A$ 换为均匀矩阵。随后每行 $r^TA$ 由剩余哈希引理的有限输出集版本接近均匀， $N$ 行的联合距离可用逐行替换界为 $N\eta_0$ 。矩阵 $\mu\operatorname{BD}^{-1}(I_N)$ 只是对均匀矩阵加一个固定偏移，因此隐藏消息；再应用公开的 BD 不增加区分能力。

每份 Flatten 后的密文有 $N^2$ 个比特，与已求值的门数无关；朴素每门矩阵乘法用 $O(N^3)$ 次模运算，解密只需一行与 $v$ 作内积，即 $O(N)$ 次模运算。 $N,q$ 与噪声参数可依赖预选深度 $L$ ，不能把这个依赖从性能结论里抹掉。

本构造的矩阵格式直接维持固定维数，不需要先乘成秘密的平方再做重线性化。若希望在固定噪声参数下继续更深计算，可研究自举；公开加密私钥带来的安全条件需另外证明，原有 LWE 公钥混合并未自动包含它。

参考资料

[1] Craig Gentry, Amit Sahai and Brent Waters, Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, CRYPTO 2013，§1.3 的 BitDecomp/Flatten 恒等式，§§3.1–3.3 的加密、安全与 NAND 运算。

形式陈述 ​

密钥、加密与一位解密 ​

三个位怎样保住一个内积 ​

一个NAND门的完整误差账本 ​

Flatten没有洗掉噪声 ​

反向链接

形式陈述

密钥、加密与一位解密

三个位怎样保住一个内积

一个NAND门的完整误差账本

Flatten没有洗掉噪声