以下文章来源于中国科学杂志社 ,作者许光午,王小云
《中国科学》杂志社是国内最具影响的科技期刊出版机构之一,目前主要产品包括《中国科学》系列、《科学通报》、《国家科学评论》和《能源化学》等21种科技期刊,旨在见证中国科学发展,促进国际学术交流。
对格理论的追本溯源足以把我们带到几百年之前。例如费马以及后来一批杰出的数学家关于一类特殊的丢番图方程的求解,还有稍后的关于堆球问题的格论表述。我们要特别指出的是秦九韶所记载的大衍求一术的算法过程里也自然地包含了求解那类特殊的丢番图方程的格论信息。格论作为一个数学分支的起点是闵可夫斯基观察到n维欧氏空间中几何图形的一些性质可以导致对数论有深远影响的优美结果,于是产生了数的几何且使格理论的影响不断地深入到数学的许多方向。
信息与计算技术的快速发展,使格理论在更多的领域里找到了应用。在格中寻找最短非零向量的难度依维数增加而增加,且是指数型增加,因此很多计算问题也更具有挑战性。在上世纪九十年代,一个有着非常密码学意义的精彩结论被刻画和证明,这就是Ajtai所建立的关于一些格论困难问题在最坏意义下的复杂性与平均意义下的复杂性的关联。在这样的框架下,密码学体制的安全性便有了更多的理论判断与保障。格的密码应用的一个巨大推动力是量子计算机的发展。在量子计算模型下,当前常用的基于因子分解和离散对数求解困难问题的公钥体制将会被攻破。所幸的是格密码体制被认为是量子计算时代的安全屏障,而且越来越多的研究者在开展后量子格密码学的研究。这样的形势也会进一步推动对格的计算方面更加广泛和深入的探索。
在过去的十几年里,我们团队就格的计算问题和它的密码学应用展开了系列研究。在格计算和格密码分析中的一些关键问题上取得了进展。我们在最短向量的计算方面提出了几个新算法,包括两层筛的启发式随机筛法和正交枚举算法,其中一些方法还在最短向量的挑战中得到测试和应用,取得过领先的成果。我们的另一个研究方向是格密码学的分析与设计。在这方面,我们发展了全新的理论框架,对于常用格密码学的错误分布的傅里叶分析性质首次提出了局部化的思想,得到了更加精细的判断安全性的区分结果。
论文信息
许光午,王小云. 格的计算和密码学应用. 中国科学:数学,2020,50:1417–1436
作者简介
王小云
许光午
山东大学网络空间学院教授。研究领域包括密码学,算法数论,和泛函分析。
来源:中国科学杂志社