同态乘法后的重线性化

形式陈述

两个线性密文相乘后，解密表达式会出现秘密的平方。重线性化用公开的辅助密文替换这些高次秘密项，把密文长度压回原来的形式。[1, §3.2]

先固定一个标量教学模型。密文为 $c=(c_0,c_1)\in\mathbb Z_q^2$ ，按模同余运算， $q\ge3$ 为奇数，秘密为整数 $s$ ；其中心化解密相位满足

[c_0+c_1s]_q=\mu+2e,\qquad |\mu+2e|<q/2.

$[\cdot]_q$ 表示取 $(-q/2,q/2]$ 中的代表，输出该整数模2的值。这里采用低位消息编码；它与Regev 加密的半模数偏移编码不同，不能把二者的乘法公式混用。实际高维 LWE 或环方案还要指定向量/多项式结构与误差分布；这个一维模型只用来解释操作，不宣称安全。

两个输入相乘，先得到长度三的系数

(w_0,w_1,w_2)=(c_0d_0,\ c_0d_1+c_1d_0,\ c_1d_1)\pmod q,

因为

(c_0+c_1s)(d_0+d_1s)=w_0+w_1s+w_2s^2\pmod q. \tag{1}

选基数 $B\ge2$ ，令 $\ell=\lceil\log_Bq\rceil$ ，把 $w_2$ 的标准代表展开为

w_2=\sum_{j=0}^{\ell-1}d_jB^j,\qquad0\le d_j<B.

公开求值密钥 $K_j=(k_{j,0},k_{j,1})$ ，要求它们满足

k_{j,0}+k_{j,1}s=B^js^2+2\epsilon_j\pmod q. \tag{2}

服务器输出

c'=\left(w_0+\sum_jd_jk_{j,0},\quad w_1+\sum_jd_jk_{j,1}\right)\pmod q. \tag{3}

式 (3) 不需要知道 $s$ ，但密钥生成方必须按具体安全构造产生式 (2) 的掩码。这里所谓“加密 $B^js^2$ ”指具有该相位关系的求值材料，并非把超出一位消息空间的整数硬塞进普通一位加密接口。

直觉

乘法把原来的秘密基 $(1,s)$ 扩成 $(1,s,s^2)$ 。重线性化提供一份公开的“替换字典”：每个 $B^js^2$ 都有一个仍用 $(1,s)$ 解密的带噪表示。

将公开系数 $w_2$ 拆成小数字后，只需按这些数字组合字典项。之所以先拆位，是因为直接用可能接近 $q$ 的大系数乘一份含噪字典项，会同步把误差放大近 $q$ 倍。

例子与边界

取 $q=257,s=3$ ，两份教学密文为

c=(252,2),\qquad d=(249,3).

它们的相位分别为 $252+6=258\equiv1$ 与 $249+9=258\equiv1$ ，都表示消息1、误差零。相乘的系数为

(w_0,w_1,w_2)=(40,226,6).

核对： $40+226\cdot3+6\cdot9=772\equiv1\pmod{257}$ 。乘法后仍正确，只是秘密基里多了 $s^2$ 。

用二进制 $6=2+4$ ，只有 $d_1=d_2=1$ 非零。选两份演示求值材料

K_1=(8,4),\qquad K_2=(17,7).

它们满足 $8+4\cdot3=20=2s^2+2$ ，以及 $17+7\cdot3=38=4s^2+2$ ；各自 $\epsilon_j=1$ 。式 (3) 给出

c'=(40+8+17,226+4+7)=(65,237).

现在只用线性秘密即可解密： $65+237\cdot3=776\equiv5\pmod{257}$ ，而 $5=1+2\cdot2$ 。输出消息仍为1，新误差为2，恰是两份辅助误差之和。

把式 (2) 代入式 (3)，得到关键不变量

c'_0+c'_1s =w_0+w_1s+w_2s^2+2\sum_jd_j\epsilon_j\pmod q.

因此重线性化只多加入一项可核算的误差。如果原输入相位为 $\mu_1+2e_1$ 、 $\mu_2+2e_2$ ，乘法阶段的误差为

e_{\times}=\mu_1e_2+\mu_2e_1+2e_1e_2.

重线性化后则为

e'=e_{\times}+\sum_jd_j\epsilon_j.

若每项 $|\epsilon_j|\le E_{\mathrm{key}}$ ，新增误差至多 $\ell(B-1)E_{\mathrm{key}}$ 。这是一项增加，不是噪声刷新。还须检查中心化相位没有越过 $q/2$ ；否则模奇数 $q$ 的回绕会改变最后模2的结果。

基数较大使 $\ell$ 较小、辅助密钥较短，但每位最大值 $B-1$ 更大。实际参数在存储、计算和误差之间取舍。标量操作需要 $O(\ell)$ 次模乘加，求值材料含 $2\ell$ 个模 $q$ 元素；环方案还要乘入其多项式运算成本。

推论与应用