跳至主要内容
全部题解
团队题解密码学

R3CTF 2026

HEuristic

利用有界噪声的系数泄漏,恢复隐藏的 CKKS 乘数。

发布日期
类别
密码学

服务只允许三种操作:加密、解密与提交。加密会先用一个隐藏标量乘以每个明文系数,再进行 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