3.1.3 Regev 归约：从 GapSVP 到 LWE (量子归约与经典归约)

文档摘要

3.1.3 Regev 归约：从 GapSVP 到 LWE (量子归约与经典归约) 我们来直面一个在格密码学中堪称“思想奇点”的时刻：2005年，Oded Regev 在 STOC 上发表那篇划时代的论文《On Lattices, Learning with Errors, Random Linear Codes, and Cryptography》，首次给出了从最坏情况下的格问题 GapSVP（带间隙的最短向量问题）到平均情况下的LWE（学习带错误问题）的严格归约——而且这个归约不仅是多项式时间的，更关键的是：它在量子模型下成立；而稍作调整后，甚至能在经典图灵机上实现。