返回学习路线

单元终点任务：审计一份私有查询与密文计算方案 ​

任务背景 ​

你收到一份技术说明，声称“加密了地址，所以一次只会泄漏一条记录；换小模数可以恢复全部噪声预算；自举后密文与新鲜加密相同”。下面用四项数据库和三个可复算账本，判断其中哪些结论真正得到证明。

小模数只用来检查代数，不能当作安全参数。关于噪声、自举与安全性的抽象契约，会在题目中明确给定；不要求从一个一维玩具例子推出真实 FHE 安全。

题目 ​

A. 查询正确性、通信与恶意查询 ​

服务器保存 $D=(1,0,1,1)$，索引从0开始。客户端要读 $D_2$。

1. 用Paillier公理库Paillier 加法同态加密Paillier cryptosystem通过n次剩余类隐藏模n明文，用L函数恢复消息，并完整核算模225的加法同态、回绕与重随机化例子。的加法同态构造 one-hot 查询。为了手算，取 $n=15,g=16$，四个随机因子为 $(2,4,7,11)$。写出四份查询密文、服务器响应公式和恢复结果
2. 若恶意客户端把四个选择位都改成1，回答是什么？这是否破坏普通 PIR 查询隐私？是否满足“只得到一条记录”的数据库隐私？
3. 改用加密二进制索引公理库单服务器计算私有信息检索Computational private information retrieval · Single-server computational PIR用加密索引与公开查表电路构造单服务器计算PIR，证明查询隐私并分别核算通信、服务器工作和数据库隐私边界。，写出两位地址和四个选择项。对比两种查询的密文数量
4. 若推广到 $N=2^k$ 条一位记录，写出多路选择树的门数、深度、服务器工作与在线通信，另说明首次公钥材料如何计费

B. 两种表示变换不能混称降噪 ​

首先采用重线性化公理库同态乘法后的重线性化Relinearization在明确的模数与低位消息模型中，把同态乘法产生的秘密平方项用基数分解和求值密钥压回线性密文，并核算新增噪声。正文的低位消息模型，$q=257,s=3$。乘法产生 $(w_0,w_1,w_2)=(40,226,6)$。

1. 二进制方案用 $6=2+4$、$K_1=(8,4)$、$K_2=(17,7)$。算出两坐标结果、消息与误差
2. 改用基数4。取 $K_0=(5,2)$，它的相位为 $s^2+2$；取 $K_1=(17,7)$，相位为 $4s^2+2$。用 $6=2\cdot 1+1\cdot 4$ 计算结果。比较两种基数的位数、实际新增误差与统一最坏上界
3. 再切换到模数切换公理库同态密文的模数切换Modulus switching逐坐标缩放舍入LWE型密文，推导消息编码偏移与秘密范数造成的新误差，区分绝对噪声变小、相对噪声和BGV保明文舍入。的高位消息模型，$q=257,p=67,s=2,c=(155,10)$。逐项算出新坐标和式 (1) 的三项误差，解释为什么不能把这里的新误差与前两问直接接成同一条加密执行

C. 深度三电路的噪声证书 ​

考虑平衡的三层 NAND 树，共8个输入，明文依次为

$$(1,1,1,0,1,0,1,1).$$

本题给定的抽象契约如下：每份新鲜密文误差界为1；每个 NAND 门的左、右输入误差界为 $E_1,E_2$ 时，输出界为 $E_1+34E_2$；解密充分阈值为 $T=65537/8$。另给一个已正确实现、允许用于当前合法密文的刷新接口，它把输出误差重新控制在4以内。本题前三问的刷新还保证输出仍在与未刷新输入兼容的同一求值密钥下，可直接送入同一个 NAND 门；可采用同钥刷新，但其公开辅助材料的安全性另按第四问审查。这个刷新契约是题设，不是声称正文那组微小维数参数已经构造出可自举安全方案。

1. 算出三层明文，以及不刷新时每层的统一误差界。最终是否仍有正确性证书？
2. 在第二层之后刷新两份密文，第三层输出误差界是多少？
3. 能否只刷新一份？分别让刷新结果处于最后一门的左输入和右输入，核算差别。为什么调换输入不会改变 NAND 明文，却会改变这份保守误差证书？
4. 刷新材料若是同一公钥下的加密私钥位，基础 CPA 证明是否已经够用？若改为两级独立密钥链，最后应使用哪把私钥？

D. 电路隐私与噪声淹没 ​

某人想在响应前增加均匀整数噪声 $Z\in \{-1000,\dots ,1000\}$，以掩盖绝对值至多4的旧残差。

1. 在一维残差模型中，与只按输出生成的参考噪声相比，总变差距离上界是多少？两种电路残差分布之间的界是多少？
2. 若解密阈值仍为上题的 $T$，本例的正确性余量是否足够？若目标误差改成 $2^{-40}$，还能同时满足同一阈值吗？
3. 为什么这个残差平滑计算尚不足以证明整份密文的电路隐私公理库同态求值的电路隐私Circuit privacy在客户端知道私钥与输入随机币的观察模型中定义电路隐私，用一位标签反例和精确平移分布距离解释为何CPA与噪声刷新都不够。？
4. 分别判断：索引保密、结果正确、数据库隐私、结果认证，哪几项已经由这份方案及给定契约证明？

完整解答 ​

A. 私有地址不等于只泄漏一项 ​

索引2的 one-hot 明文为 $(0,0,1,0)$。用 $\mathrm{Enc}(m;r)={16}^m{r}^{15}mod225$，得到

$$(Q_0,Q_1,Q_2,Q_3)=(143,199,88,26).$$

服务器返回

$$A=\prod _{j=0}^3{Q}_j^{D_j}mod225=143\cdot 88\cdot 26mod225=34.$$

${34}^{4}mod225=61$，因此 $L(61)=4$，再乘解密逆元4模15得到1，正是 $D_2$。服务器没有直接读取 one-hot 的哪一位为1。

若查询改成全一明文，响应解密为 $1+0+1+1=3(\mathrm{mod}15)$。这个和不属于“返回某个指定数据库位”的理想输出，因此不满足恶意客户端的单项数据库隐私。查询隐私是另一个方向：它要求服务器辨认不了诚实查询中的索引，并没有保证客户端遵守 one-hot 约束。玩具参数当然不具真实查询隐私；上述隐私归约指安全参数下的 CPA 假设。

二进制索引为 $(b_1,b_0)=(1,0)$，四个选择项为

$$((1-b_1)(1-b_0),(1-b_1)b_0,b_1(1-b_0),b_1{b}_0)=(0,0,1,0).$$

客户端只发两份索引密文；服务器通过非线性同态求值生成选择效果。one-hot 发四份密文，只需线性同态。一般情况下，前者为 $k$ 份查询密文，后者为 $N$ 份。

二选一树有 $N-1$ 个选择器、$k$ 层。朴素服务器做 $O(N)$ 次选择器求值并访问整库；在线查询为 $k{\ell }_{\mathrm{ct}}$ 位，回答为 ${\ell }_{\mathrm{ct}}$ 位。首次的 $pk,evk$ 长度另外加入；若它们或 ${\ell }_{\mathrm{ct}}$ 依赖预定深度 $k$，该依赖也要保留。

索引隐私的归约依次替换 $k$ 份地址位加密，最多损失 $k$ 倍单次 CPA 优势。服务器的计算只是这个查询的高效后处理。协议若额外泄漏索引相关的长度、时序或解密失败反馈，就已超出这份证明。

B. 基数改变长度与误差，编码改变语义 ​

二进制结果为

$$(40,226)+(8,4)+(17,7)=(65,237)(\mathrm{mod}257).$$

相位 $65+3\cdot 237\equiv 5=1+2\cdot 2$，消息1，新增误差2。基数4的结果为

$$(40,226)+2(5,2)+(17,7)=(67,237)(\mathrm{mod}257),$$

相位模257为7，即 $1+2\cdot 3$，消息仍为1，新增误差3。

覆盖全部系数 $0\le w_2<257$ 时，二进制需要 $\lceil {\log }_{2}257\rceil =9$ 个数字，基数4需要 $\lceil {\log }_{4}257\rceil =5$ 个。若每份辅助误差绝对值至多1，通用上界分别为 $9(2-1)=9$ 和 $5(4-1)=15$。这个上界不利用最后一位的额外限制，因而是保守的；实际系数6只使用了其中少量数字。

高位编码的换模例子则为

$$(155,10)⟼(40,3),155-2\cdot 10=128+7,40-2\cdot 3=33+1.$$

三项误差分别为 $469/257$、$-307/257$、$95/257$，总和为1。前两问的消息是中心化小相位的奇偶，第三问的消息由0与半模数中心判别；它们采用不同编码与解密算法，不能把数值相邻的“误差”当作同一条方案的数据流。实际组合必须使用匹配的消息保持规则。

C. 不仅看层数，还看误差进入哪一侧 ​

第一层 NAND 的明文为 $(0,1,1,0)$，第二层为 $(1,1)$，第三层为0。

不刷新时，每层两边统一使用同一上界，所以递推为 $E\mapsto 35E$，得到

$$1⟼35⟼1225⟼42875.$$

$T=8192.125$，最后一层的充分证书失效。这里不能写“必然解错”；它只表示现有上界无法证明正确。

若把第二层两份密文都刷新为误差至多4，最后一门得到

$$4+34\cdot 4=140<T.$$

其实只刷新一份也能成功，但方向重要。刷新左输入时，界为

$$4+34\cdot 1225=41654>T;$$

刷新右输入时，界为

$$1225+34\cdot 4=1361<T.$$

原因来自 GSW 乘法误差 ${\mu }_2{e}_1+C_1{e}_2$：右输入误差被整个左矩阵乘，保守行和系数是34。NAND 的明文运算交换对称，但密文矩阵不必交换，误差估计也不对称。把噪声较小的刷新密文放在右侧，可在这个预算中省去一次刷新。

若刷新公开 ${\mathrm{Enc}}_{pk}(sk)$，需要覆盖该辅助信息的循环安全或密钥相关消息证明。普通未带辅助材料的 CPA 结论不足。独立链 $p{k}_0\to p{k}_1\to p{k}_2$ 则可用逆序混合处理，最后刷新结果须由 $s{k}_2$ 解密；公钥材料也随链长增长。若只把最后一门的一份输入从 $p{k}_0$ 刷新到 $p{k}_1$，它不能直接与仍在 $p{k}_0$ 下的另一份密文相乘。必须同步切换另一输入，或另行提供经过证明的兼容接口，并重新计入噪声与成本；独立密钥链不能免费沿用上面的1361结论。

D. 平滑一项分布，还没有完成完整模拟 ​

对任意 $|e|\le 4$，

$$\mathrm{\Delta }(Z+e,Z)\le \frac{4}{2001}\approx 0.001999.$$

两种电路残差之间的距离至多 $8/2001$。正确性上，总残差绝对值至多1004，小于 $T$，所以这一维契约允许它。

若希望单份分布与参考分布距离不超过 $2^{-40}$，则要有

$$2M+1\ge 4\cdot 2^{40},M+4<T.$$

第二式限制 $M$ 只有约八千，第一式却需要约 $2^{41}$，两者不可能同时成立。要达到更强统计隐私，需要重新安排参数或采用另一种完整转换，不能只把“可忽略”写进结论。

完整电路隐私还必须模拟客户端知道私钥、消息、原随机币时所见的整份密文。若别的坐标含有门数标签，或与被平滑噪声存在可见相关，式子只处理一维残差，无法消除这些泄漏。自举保证的误差界也不自动等于这种分布模拟。

最终结论分四项：

• 索引保密：在真正安全参数与包含全部求值材料的 CPA 假设下，由逐位混合证明；小模数演示不承担安全性
• 正确性：对诚实查询/服务器，由同态正确性和本题给定的有效噪声证书保证；不能把失败的上界证书写成保证
• 数据库隐私：未证明，全一查询已给出反例；诚实输入的电路隐私与恶意输入约束还需分别解决
• 结果认证：未证明，服务器仍可能返回错误结果；需要额外的验证机制

验收标准 ​

• 能得到实际密文 $(143,199,88,26)$ 与响应34，而不只是写“同态相加”
• 明确指出 one-hot 查询的线性通信，以及加密索引换取的非线性求值工作
• 区分低位消息与高位消息编码，列出换模时全部三项残差
• 深度三预算得到42875，并找到仅刷新右输入时的1361证书
• 不把功能可自举与循环安全混为一个假设
• 电路隐私比较保留客户端私钥和随机币，不只看解密输出
• 分别汇报查询隐私、正确性、数据库隐私与结果认证

下载 Python 复算脚本。脚本只使用标准库，包含模225全部消息/随机因子的14400组同态加法、真实带噪GSW小矩阵的32次NAND检验，以及257²组坐标的换模恒等式；这些有限检查不证明密码学困难性。