同态密文的模数切换

形式陈述

模数切换把模 $q$ 的密文转换到较小模数 $p$ ，同时尽量保持解密消息。它不是仅把每个整数取模 $p$ ；核心动作是先按比例 $p/q$ 缩放，再舍入。[1]

先采用Regev 型高位消息编码。设密文 $c=(v,u_1,\ldots,u_n)$ ，整数秘密向量 $t=(1,-s_1,\ldots,-s_n)$ ，满足

\langle c,t\rangle=\mu\Delta_q+e+kq, \qquad \Delta_q=\lfloor q/2\rfloor,\quad\mu\in\{0,1\}.

$c$ 的坐标取固定整数代表， $k$ 吸收模回绕， $e$ 是相对编码中心的小整数残差。令 $3\le p<q$ ，逐坐标定义

c'_j=\left\lfloor\frac pq c_j\right\rceil,\qquad \rho_j=c'_j-\frac pqc_j,\qquad |\rho_j|\le\frac12.

平局采用固定舍入规则；计算后可以再模 $p$ 。写 $\Delta_p=\lfloor p/2\rfloor$ ，则

\langle c',t\rangle=\mu\Delta_p+e'+kp,

\boxed{e'=\frac pqe+\langle\rho,t\rangle +\mu\left(\frac pq\Delta_q-\Delta_p\right).} \tag{1}

把 $t^T$ 看成实数行矩阵，其诱导无穷范数是绝对行和 $\|t\|_1$ ，故

|e'|\le\frac pq|e|+\frac12\|t\|_1+ \left|\frac pq\Delta_q-\Delta_p\right|. \tag{2}

若右侧严格小于 $\Delta_p/2$ ，按新模数的两中心判决仍正确。最后的编码项小于1，不能在奇模数之间无说明地删掉。式 (1) 是代数正确性关系；换模后的分布是否符合某项安全假设是另一个问题。

算法对 $n+1$ 个坐标分别执行整数乘法、除法与舍入，共 $O(n)$ 次缩放舍入操作，不需要私钥。每次操作的位成本取决于 $\log q$ ，因此不能把模数位长当作免费常数。

直觉

想象把模圆周连同消息中心一起缩小。若能保留实数坐标，旧噪声就会恰好乘以 $p/q$ ；但密文必须仍由整数构成，因此每一坐标要向附近格点舍入。

解密不是分别看各坐标，而是与秘密向量作内积。一个半单位的舍入误差，乘上绝对值34的秘密坐标，就可能变成17。短秘密之所以重要，来自这个实际放大，而不是“模数越小噪声自然越小”的直觉。

例子与边界

取秘密 $s=2$ 、 $t=(1,-2)$ 、 $\mu=1$ ，密文 $c=(v,u)=(155,10)$ 。旧相位为

155-2\cdot10=135=128+7,

故旧误差为7。缩放舍入得到

v'=\left\lfloor\frac{67\cdot155}{257}\right\rceil=40, \qquad u'=\left\lfloor\frac{67\cdot10}{257}\right\rceil=3.

新相位为 $40-2\cdot3=34=33+1$ ，新误差确为1。分别看式 (1) 的三项：

\frac pqe=\frac{469}{257},\quad \rho_v-2\rho_u=\frac{-105-202}{257},\quad \frac pq\Delta_q-\Delta_p=\frac{95}{257}.

相加恰为 $257/257=1$ 。这次舍入项与旧误差相抵消，但通用上界不能指望每次都有这种好运。

仍取 $q=257,p=67$ ，现在 $s=34$ 、 $c=(7,140)$ 。旧相位

7-34\cdot140=-4753=130-19\cdot257

对应消息1、误差2。缩放后的坐标为 $(2,36)$ ，新相位模67为

2-34\cdot36\equiv51\pmod{67}.

51离消息中心33为18，离0只需绕回16，于是新解密为0。旧噪声很小仍不足以保证成功；舍入误差经秘密坐标放大，越过了新判决边界。此例是相位恒等式的教学演示，不声称大或小的一维秘密有密码学安全性。

忽略舍入时， $e'=(p/q)e$ ，所以 $|e'|$ 变小，但

\frac{|e'|}{p}=\frac{|e|}{q}.

相对间隔没有凭空扩大；加入舍入后还可能略差。模数切换可以缩短表示，并在特定同态编码的逐层分析中抑制后续误差增长，但它不等于恢复一份新鲜噪声分布。

推论与应用

BGV 型教学关系常写成 $\mu=[\langle c,t\rangle]_q\bmod r$ ，这里 $r\ge2$ 为整数，消息藏在小相位的模 $r$ 值里，而不是0与半模数之间的距离。这时普通最近整数舍入未必保持消息。

若 $q\equiv p\equiv1\pmod r$ ，可把 $c'_j$ 选为离 $(p/q)c_j$ 最近、并满足 $c'_j\equiv c_j\pmod r$ 的整数。每坐标舍入误差至多 $r/2$ 。设旧中心化相位为 $h=\langle c,t\rangle-kq$ ，则候选新相位为

h'=\langle c',t\rangle-kp =\frac pqh+\langle\rho,t\rangle.

只要 $|h'|<p/2$ ，它就确实是新中心化相位。又因坐标保模 $r$ 、 $p\equiv q\pmod r$ ，有 $h'\equiv h\pmod r$ ，消息保持。充分条件可写为

\frac pq|h|+\frac r2\|t\|_1<p/2.

这个条件、舍入约束和高位编码的式 (1) 是两套匹配关系，不能各取一半拼起来。[1, Definition 6 and Lemma 4]

例如 $r=2$ 、仍用 $q=257,p=67$ 、 $t=(1,-2)$ ，取 $c=(29,10)$ ，旧相位为9，消息为1。普通舍入给 $(8,3)$ ，新相位2，错误变成0。要求保留各坐标奇偶后，最近选择为 $(7,2)$ ，新相位3，仍为1。

在固定密钥已知正确的密文上，公开确定性换模只是后处理，不会增加外部观察者已有的区分能力。不过“所得样本就是某组新参数的标准 LWE 样本”是更强的分布声称，需要单独归约，不能由式 (1) 自动推出。

重线性化控制秘密基的维数，模数切换控制数值尺度与表示位数；自举则同态求值解密。规划深电路时，应把三者的成本与正确性余量分别计入。

参考资料

[1] Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan, Fully Homomorphic Encryption without Bootstrapping, ECCC TR11-111, 2011，§3.3，Definition 6、Lemma 4、Corollary 1；§4.3 的模数阶梯。本文式 (1) 单独推导高位消息编码的缩放误差，随后明确切换到原文的保模明文约定。