服务只允许三种操作:加密、解密与提交。加密会先用一个隐藏标量乘以每个明文系数,再进行 CKKS 编码;解密则会暴露前几个系数,并附带幅度很大但严格有界的加性噪声。
这已经足够。关键并非直接消除 CKKS 噪声,而是让连续泄漏彼此形成足够严格的约束,使每一步都只剩下唯一可行的模提升结果。
构造明文
对于明文模数 q,我们选择如下形式的系数:
coefficient[i] = q // 2 + 5**i从每个解密系数中减去共同基线后,得到的观测值等价于:
z[i] = 5^i * delta + error[i] (mod q)基线保证每个提交的系数都处于服务允许的范围内。五的幂则建立了模提升所需的递推关系。
在噪声中逐步提升
设 L[i] 为 z[i] 选定的整数提升值。下一个真实值大约是前一个值的五倍:
L[i + 1] ≈ 5 * L[i]每个剩余类都有无限多个相差 q 的代表元。对每个新样本,我们选择与 z[i + 1] 同余、且最接近 5 * L[i] 的那个代表元。
题目给出的噪声上界保证了这个选择是唯一的:相邻样本之间累积的误差始终远小于模数的一半。对足够多的系数重复这一过程后,5^i * delta 会增长到远高于噪声底限。
恢复并验证
在最后一个样本上,普通四舍五入就能恢复隐藏标量:
delta = round(lifted[-1] / 5**last_index)提交前,我们用每一个泄漏的系数验证该值。服务接受了恢复出的结果。
关键结论
近似加密并不代表结构化泄漏无害。当攻击者能够控制相关明文,而服务又暴露足够多相互关联的系数时,有界误差本身就可能成为可利用的约束。
赛事页面:CTFtime 上的 R3CTF 2026。
