AI Grinding for Fun and Cryptanalysis
Lukasz Olejnik, Bartosz Naskrecki
cs.CR
2026-08-22
把大模型当高产量猜想器,精确算术和对照实验才算证据。8 个已发表构造在作者自己声明的参数上失败,每条都带可复现见证。
大模型读完一篇密码论文,能吐出一堆攻击路径。几乎全是错的,而且错得很整齐:写得流畅,往「已经破解」那边夸,把证明缺口和真正的 break 混在一起。贵的是判定哪条招是真的。
Olejnik 和 Naskrecki 把判定做成一套叫 grinding 的流程,中文里可以叫研磨。生成端故意做得又多又糙;模型说的话一律不算证据。精确算术、事先写死预期结果的对照实验、对照到具体版本的原文,这三样过了才准入。活下来的结果还要拿它自己的局限当下一刀,直到打破论文承诺的安全性质,或者撞上可以写成证明的墙。
密码分析向来奖励一个人把一个想法推很远。这篇不替代那种深度,它要的是可复现的候选,再交给人定级。
搜索对准论证里的接缝:换代数、换编码、分布穿过映射、取整或 CRT、商、零这种例外值、量词变宽、参数塞进脚本却没塞进定理。到了接缝只问两句。
公开对象上还活着哪条高效可算的映射,会把该藏的关系变得平凡或可枚举。实际出来的分布是不是证明里写的那条律。两个问题都不要求先读懂整套构造,所以可以丢给只读过一篇论文的生成器。
循环很短:想法落到精确见证,见证往往带着「只在某某条件下成立」,再打这条条件,得到更强的攻击,或者得到一条推不动的边界。后者也算结果。准入必须是短的确定性程序能核的等式,外加一个事先固定结果的对照。机器管猜想的宽度,人管后果、范围和出处。
八个已发表构造,在作者自己写下的参数或声明上失败。群环判定和多元 MinRank 加固停在假设或记账层,故意没算进「构造被破解」。另外三个目标没打出攻击,只说明 Sparse、Tensor、Succinct LWE 的通用读法比定理覆盖更宽。
| 目标 | 被打掉的声明 | 数字 |
| Ring-LWR 承诺 | 绑定性,以及三个协议的可靠性 | 允许的乘子里有 d=0,零承诺对任意消息都以概率 1 打开;抽取器在约一半挑战对上除以零因子 |
| Spinel 签名哈希 | 碰撞与第二原像 | 255 个非零字节里 244 个有立刻第二原像;可打印等长对 "(y" 与 "y(" 映到同一摘要 |
| 中间积加密,印出来的 t=9 | IND-CPA | 一张密文收回全部 2313 个二元掩码,成功概率至少 0.999999730074;攻击撑到 t=24,t=25 塌掉;方案自己的引理要 t≥98 |
| 格电子投票 | 无收据性 | 假收据模拟器与真卷积律的总变差至少 1/15,任意允许的三元参数都修不好;d=4096、p=1/3 时零系数计数的优势是 0.999999804160 |
| Hollow-LWE 可更新加密 | 更新前密文的 IND-CR-CPA | 已知置换后,线性代数收回合法旧解密钥,缩维三档各 12/12;同时修维度记账和 Schur 弱区,密文和更新令牌放大 1.24 到 1.54 倍 |
| 双肢 CRT-RLWE | 带认证载荷后恶意重随机化只造成拒绝服务 | 接受位是噪声的阈值预言机,n=4096 时至多 131072 次自适应反应收回密钥 |
| 函数域 Normal Ring-LPN | 印出来的 63 次显式正规基实例 | X^63+X^7+1 裂成七个 9 次不可约因子,3584 次候选测试代替 2^63 |
| 半直积群环 LWE | 全环及选定商上的判定困难 | 两样本区分的一致假接受界是 64 N^{-7} log^2 N,属假设缺陷 |
这些失败都停在困难问题的上一层。还没碰到格约化,零乘子、无边界的变长编码、多项式乘积的两端系数、模拟器边缘分布,已经把声明弄垮。
给写方案和审稿的人,处方很窄。新代数层或新表示一旦加上去,安全论证要枚举公开对象上高效可算的像,并说明秘密在那里不可枚举、投影误差不可区分。输入编码先证明单射或唯一可解码,再谈把哈希安全性搬过去。验证器接受的是一个集合,绑定性就要对整个集合证,不能只对诚实打开证。参数脚本必须在归约真正给出的维度上调用估计器。
给做 AI 辅助研究的人,有用的拆分是生成器可靠性和证据可靠性。生成可以又多又糙,准入边界必须精确、带对照、对人可复现。模型不必可靠,研究才站得住。这是方法上的渐进贡献,不是新原语。
Hollow-LWE 实验假定置换已经收回,只在缩维上验证后续代数,不是全尺寸置换恢复的基准,那一步是别人的工作。MinRank 数字停在源论文自己的代价公式里,没有跑通密钥恢复。Spinel 的消息摘要 Hmsg 如果仍用常规哈希,碰撞到不了伪造;源文只钉了可调哈希。CRT-RLWE 攻击依赖接受和失败可被观察;收件端完全不暴露差异,就没有预言机。群环结果只收回秘密在公开映射下的像,源文也没有 Type-II 参数生成器和消息编码,打不到一个完整加密方案。
研磨交出来的是可复现候选,定级权在人。作者把覆盖缺口和失败的加强尝试单独记下,避免一份全是破解的清单看起来像未知过滤器。