USTC paper: matrix multiplication exponents below 9/4 would also speed up lattice sieving
jedisct1 · x · 2026-10-26
A new IACR ePrint preprint (2026/2622) by Yiming Gao and Honggang Hu of USTC, Faster Matrix Multiplication Leads to Faster Lattice Sieving, shows that under the spherical heuristic used in the BDGL analysis, if the matrix multiplication exponent ω ≤ 9/4−η for any fixed η>0, heuristic lattice sieving improves to (3/2−δ)^(n/2+o(n)) time.
Since OpenAI recently showed ω ≤ 9/4, any further speedup in matrix multiplication would directly cascade into lattice sieving — the core operation underlying lattice-based cryptography's security estimates. With known matrix multiplication algorithms, the method already yields subquadratic search within BDGL buckets. The authors ask whether the result generalizes to non-square (rectangular) matrix multiplication, which is faster than square. Shared via cryptographer jedisct1 relaying hashbreaker's commentary.
More from Research
- RCT: ChatGPT temporarily boosts consultants' data science skills, gains vanish without it — EricTopol · 2026-10-26
- FocusVLA routes robot camera views by predicted interaction intent across task stages — iscas-cloud · 2026-10-26
- Transformers' biggest audio overhaul: unified AudioProcessor architecture — LysandreJik · 2026-10-26
- Free 195-page primer: The Little Book of Generative AI Foundations — caglar_ee · 2026-10-26
- SPADER from Zhejiang and Peking University Tops All Four Multi-Answer QA Benchmarks, Accepted at EMNLP — jiqizhixin · 2026-10-26
- Purdue's GPS-free autonomous drone tracks runners through dense forests using on-chip LiDAR AI — KordingLab · 2026-10-26