中科大论文:若矩阵乘法指数低于 9/4,格密码筛法也将提速
jedisct1 · x · 2026-10-26
中国科学技术大学 Yiming Gao 与 Honggang Hu 在 IACR ePrint 发布预印本《Faster Matrix Multiplication Leads to Faster Lattice Sieving》(2026/2622)。
核心结论:在 BDGL 分析所用的球面启发式下,若矩阵乘法指数 ω ≤ 9/4−η(η 为任意正常数),则启发式格筛法(lattice sieving)可改进到 (3/2−δ)^(n/2+o(n)) 时间。由于 OpenAI 最近刚证明 ω ≤ 9/4,该结果意味着矩阵乘法的任何进一步加速都会直接传导到格密码的核心运算——而格筛法正是格密码安全性评估的基础。用已知矩阵乘法算法,该方法已能在 BDGL 桶内实现亚二次搜索。
作者进一步提出开放问题:该结论能否推广到非方阵乘法(矩形矩阵乘法通常更快)。这条转发评论来自密码学家 jedisct1 转发 hashbreaker 的讨论。
「研究」频道最新
- 用小开源模型逆向工程游戏二进制:主 agent 中途重写子 agent 的 harness — yb2698 · 2026-10-26
- 作者：盼合同形式化成为连接 AI 与经济学的「MDP 时刻」 — xuanalogue · 2026-10-26
- 研究发现：前沿 LLM 常为私利单方面撕毁 AI 合同 — xuanalogue · 2026-10-26
- ContractSim：首个评估 LLM 自然语言合同谈判的框架 — xuanalogue · 2026-10-26
- Partial RoPE 研究：仅旋转 10% 维度即可逼近全 RoPE 收敛 — BlancheMinerva · 2026-10-26
- 133 位专利律师实验：同样用 AI，老手被增强、新人陷入认知卸载 — xiaohu · 2026-10-26