同态加密与紧致求值

形式陈述

同态加密要回答的问题是：一个人没有解密钥匙，能否把若干密文变成某个计算结果的密文？ 从公钥加密出发，加入公开求值算法：

(pk,sk,evk)\leftarrow\operatorname{KeyGen}(1^\lambda),\qquad c_i\leftarrow\operatorname{Enc}_{pk}(m_i),

c_C\leftarrow\operatorname{Eval}(pk,evk,C,c_1,\ldots,c_t),\qquad m_C\leftarrow\operatorname{Dec}_{sk}(c_C).

$evk$ 是可选的公开求值材料，可以并入公钥；它不是允许交给服务器的明文私钥。本页只讨论同一密钥下的密文，电路 $C$ 用固定门基的Boolean 电路表示。若明文取有限环元素，先指定其比特编码，所允许的环运算也可表示为相应的 Boolean 电路；这不表示方案能求值编码上的所有 Boolean 函数。不同人的独立公钥不能直接混进这个接口。

对允许的电路族 $\mathcal C_\lambda$ ，求值正确性要求每个合法 $C$ 和每个匹配长度的明文向量 $\mathbf m$ 都满足

\Pr\!\left[ \operatorname{Dec}_{sk}\!\left(\operatorname{Eval}(pk,evk,C,\operatorname{Enc}_{pk}(\mathbf m))\right) =C(\mathbf m)\right]\ge1-\operatorname{negl}(\lambda). \tag{1}

概率包括密钥生成、各次加密及随机化求值；误差界要对所声明的电路规模范围统一成立。若要求电路和消息在看到公钥后自适应选取，就应对该实验另行给出正确性保证。只测均匀随机消息不够。

紧致性与层级参数

先固定单比特输出。紧致性要求结果密文长度与解密工作量有一个只依赖安全参数的固定多项式上界，与 $C$ 的门数、深度和原始输入数量无关。多比特输出允许再乘以输出长度。服务器求值时间当然可以随 $|C|$ 增长：外包的正是这部分工作。[1,2]

全同态加密（FHE）在一次密钥生成之后，支持任意多项式规模的电路，保持上述紧致性与正确性。层级全同态加密则先输入深度上限 $L$ ，再运行 $\operatorname{KeyGen}(1^\lambda,1^L)$ ；密钥生成与求值仍须对 $\lambda,L,|C|$ 多项式可执行。

层级方案有两种需明确区分的预算写法。较强定义仍要求最终解密电路与 $L$ 无关；参数化的实现说明常允许密文和解密成本为 $\operatorname{poly}(\lambda,L)$ ，只要求在选定参数后不随实际求值电路继续增长。本单元讨论 GSW 的固定矩阵格式时采用后一项显式预算；讨论自举得到深度无关的 FHE 时采用前一项。两者都不能把与 $|C|$ 成正比的计算记录叫作紧致结果。

基础保密目标取IND-CPA，且攻击者得到全部公开 $pk,evk$ 。若 $evk$ 含有私钥的加密，必须证明连同这份辅助材料仍安全；不能先在没有 $evk$ 的游戏里证明 CPA，再把任意求值材料无条件公开。

直觉

普通加密让密文在没有钥匙的人看来隐藏消息。同态加密再赋予密文一种可控制的运算结构：明文的门，对应公开可执行的密文变换。服务器能按接线计算，却不会因此看到中间值。

“能算”与“算得紧凑”是两道独立要求。若客户最后仍须读完整份计算记录、亲自把原电路执行一遍，服务器没有替客户完成主要工作。紧致性就是把这条要求写进长度和解密成本。

上路先对明文执行电路，下路先加密再公开求值；最后解密应汇合于同一输出，结果长度不随电路门数增长。

例子与边界

一条两门电路

设 $C(a,b,c)=(a\mathbin{\mathrm{AND}}b)\mathbin{\mathrm{XOR}}c$ ，输入为 $(1,0,1)$ 。明文路径先得到 $1\cdot0=0$ ，再得到 $0\oplus1=1$ 。

客户端分别加密三位，服务器先计算

c_{ab}=\operatorname{Eval}(\mathrm{AND},c_a,c_b),\qquad c_{\mathrm{out}}=\operatorname{Eval}(\mathrm{XOR},c_{ab},c_c).

能逐门重复调用的方案须保证求值后的密文仍属于下一门允许的输入类型，最后解出1。一个只承诺从新鲜输入求值整张电路的单次接口，不自动承诺任意再次求值；也可以把两门合成 $C$ 后一次调用。具体方案应说明采用哪一种闭包保证。

这里“与加密1相同”只说解密结果相同。它不表示求值密文与新鲜 $\operatorname{Enc}(1)$ 具有相同分布；噪声、层级标签或其他字段可能不同。后一种隐藏计算痕迹的要求属于电路隐私。

一个完全正确却没有外包计算的方案

从任何普通公钥加密构造“求值”

\operatorname{Eval}_{\mathrm{lazy}}(C,c_1,\ldots,c_t) =(C,c_1,\ldots,c_t).

解密端先解出所有输入，再运行 $C$ 。式 (1) 完全成立；输入保密也没有被破坏。但若电路有一百万门，返回值包含这百万门的描述，客户端还要执行它们。这个方案不满足紧致性。

即使把记录压成一个格式统一的文件，也不会改变它的位长和解密成本。紧致性针对资源，不针对文件数量。

保密不能替代结果认证

服务器可以返回任意错误密文，或者只返回某个输入密文。CPA 保证它难以辨认秘密输入，不保证它遵守规定电路。要核验结果，需要额外的可验证计算、认证或证明机制。

同态可塑性也会破坏普通自适应 CCA2 目标：若能把挑战位密文公开变成其翻转位密文，后者必与原密文不同，解密查询就泄漏挑战位。实际协议必须限制解密反馈并采用匹配的安全模型。

推论与应用

Paillier展示加法这一受限运算族；GSW以近似特征向量实现通用门。密文噪声会随运算增长，自举通过同态执行解密电路重新组织表示，而不是让服务器看见明文。

公开求值对输入密文只是高效后处理。若有人借助求值区分两组同长输入的加密，就可在 CPA 游戏中自行执行同样求值，得到原加密的区分器。这个论证保护的是秘密输入；它不承诺隐藏公开电路已经确定的事实，例如恒零电路的输出必为零。

在计算型私有检索中，客户加密索引，服务器求值查表电路。此时需分别核算查询长度、响应长度、服务器扫描成本和客户端解密成本，才能看清紧致性实际节省了哪部分资源。

参考资料

[1] Craig Gentry, A Fully Homomorphic Encryption Scheme, Stanford PhD thesis, 2009，§2.1，Definitions 2.1.1–2.1.7；§4.1 的深度无关解密与逐层公钥链。
[2] Zvika Brakerski, Fundamentals of Fully Homomorphic Encryption — A Survey, ECCC TR18-125, 2018，§2：紧致性、求值接口、函数隐私与单次/多次求值。

形式陈述 ​

紧致性与层级参数 ​

一条两门电路 ​

一个完全正确却没有外包计算的方案 ​

保密不能替代结果认证 ​

反向链接

形式陈述

紧致性与层级参数

一条两门电路

一个完全正确却没有外包计算的方案

保密不能替代结果认证