博文
格，实际应用中优美数学的例子
||
《中国科学：数学》发表王小云院士的创刊70周年特邀综述，介绍格理论的基本计算问题和典型的密码学应用。
许光午，王小云
对格理论的追本溯源足以把我们带到几百年之前。例如费马以及后来一批杰出的数学家关于一类特殊的丢番图方程的求解，还有稍后的关于堆球问题的格论表述。我们要特别指出的是秦九韶所记载的大衍求一术的算法过程里也自然地包含了求解那类特殊的丢番图方程的格论信息。格论作为一个数学分支的起点是闵可夫斯基观察到n维欧氏空间中几何图形的一些性质可以导致对数论有深远影响的优美结果，于是产生了数的几何且使格理论的影响不断地深入到数学的许多方向。
信息与计算技术的快速发展，使格理论在更多的领域里找到了应用。在格中寻找最短非零向量的难度依维数增加而增加，且是指数型增加，因此很多计算问题也更具有挑战性。在上世纪九十年代，一个有着非常密码学意义的精彩结论被刻画和证明，这就是Ajtai所建立的关于一些格论困难问题在最坏意义下的复杂性与平均意义下的复杂性的关联。在这样的框架下，密码学体制的安全性便有了更多的理论判断与保障。格的密码应用的一个巨大推动力是量子计算机的发展。在量子计算模型下，当前常用的基于因子分解和离散对数求解困难问题的公钥体制将会被攻破。所幸的是格密码体制被认为是量子计算时代的安全屏障，而且越来越多的研究者在开展后量子格密码学的研究。这样的形势也会进一步推动对格的计算方面更加广泛和深入的探索。
在过去的十几年里，我们团队就格的计算问题和它的密码学应用展开了系列研究。在格计算和格密码分析中的一些关键问题上取得了进展。我们在最短向量的计算方面提出了几个新算法，包括两层筛的启发式随机筛法和正交枚举算法，其中一些方法还在最短向量的挑战中得到测试和应用，取得过领先的成果。我们的另一个研究方向是格密码学的分析与设计。在这方面，我们发展了全新的理论框架，对于常用格密码学的错误分布的傅里叶分析性质首次提出了局部化的思想，得到了更加精细的判断安全性的区分结果。
我们感谢《中国科学：数学》提供的机会，促使我们整理总结格的计算和密码学应用方向上的重要事件，并力求反映它们本质的数学意义。希望我们的文章包括了对读者有益的信息，也希望能引起更多读者对这方面相关课题的兴趣。
论文信息：
作者简介
王小云
清华大学高等研究院“杨振宁讲座”教授，山东大学网络空间安全学院院长。2017年当选中国科学院院士。2019年当选国际密码协会会士（IACR Fellow）。兼任中国密码学会副理事长，中国数学会副理事长，中国科协女科技工作者专门委员会委员，中国女科技工作者协会常务理事，教育部高等学校网络空间安全专业教学指导委员会副主任委员等职。
主要从事密码理论及相关数学问题研究。在密码分析领域，提出了密码哈希函数的碰撞攻击理论，即模差分比特分析法；破解了包括全球网络广泛部署的MD5、SHA-1在内的5个国际通用哈希函数算法。哈希函数是保障网络信息可认证性、抗抵赖性和数据完整性（防数据篡改）的支撑技术，还是区块链的起源性技术。该工作动摇了国际哈希函数设计的理论根基，并导致美国NIST向全球征集了新哈希标准SHA3的五年设计工程。主持设计的哈希函数SM3成为国家标准和46个行业规范，在金融、交通、国家电网、区块链等重要经济领域广泛使用，产生巨大经济效益和社会效益。SM3算法于2018年10月正式成为ISO/IEC国际标准，向世界提供了中国密码方案和中国密码智慧。王小云将比特分析法进一步应用于带密钥的密码算法包括消息认证码、分组加密算法、认证加密算法、流密码算法的分析，给出系列重要算法HMAC-MD5、MD5-MAC、SIMON、Keccak-MAC等重要分析结果，使得比特分析方法成为对称密码领域极其重要的分析方法。2006年起专注于抗量子计算机攻击的公钥密码研究，特别是格密码研究（最受关注的下一代密码算法），给出了格困难问题求解的启发式算法二重筛法等系列算法，设计了更实用化的安全性紧的格密码算法。
多次获得顶级国际密码会议---欧密会、美密会最佳论文。获2020年国际密码协会“最具时间价值奖”（IACR Test-of-Time Awards）、真实世界密码学奖（The Levchin Prize for Real-World Cryptography）；2019 年未来科学大奖——数学与计算机科学奖；2017年全国创新争先奖状；2016年全国优秀科技工作者、网络安全优秀人才奖；2014年中国密码学会密码创新奖特等奖；2010年苏步青应用数学奖；2008年国家自然科学二等奖；2006年陈嘉庚科学奖、求是杰出科学家奖、中国青年女科学家奖等。
许光午
山东大学网络空间学院教授。研究领域包括密码学，算法数论，和泛函分析。
https://blog.sciencenet.cn/blog-528739-1256805.html
上一篇：大气化学反应的“燃料”——挥发性有机物（VOCs）
下一篇：听完这场高等数学思政课， 学渣也能热血沸腾爱上高数！
