格的极值问题的模形式算法及应用研究

摘要

格问题在现在的公钥加密方案中扮演了相当重要的角色，格问题的计算难解性为许多创新性的公钥加密方案提供了理论依据。模形式算法作为新的随机算法解决欧几里得空间内的最短格向量(SVP)和最近格向量(CVP)问题。利用此方法，不仅可以求SVP和CVP的最小的格向量的非零2-范数的值，同时还可以求出满足要求的最小格向量的个数。模形式方法主要基于格向量的2-范数的母函数和西塔函数的特殊性质。从计算复杂性的观点来看，以解决格向量问题的SVP问题为例，在所有以维度dim(Λn)=n阶hn=l(Λn)的整数格向量范围内，算法能够以（1-ε）的可能性找到最小的非零格向量同时计算出满足条件的最小非零格向量的个数，时间复杂度为(loglog(n2hn)）O(n)log(1/ε)，空间复杂度为n的多项式复杂度。确切的说，影响时间复杂度最大的因素来源于模形式算法需要独立的随机抽取格向量(loglog(n2hn)）O(n)log(1/ε)次，其余的所有的操作对于算法复杂度的影响只是n的多项式复杂度。对于计算CVP问题时，情况相同。
　　本文在阐述了格的模形式算法及其复杂性后，以此为理论基础，运用匿名的公钥加密方案和零知识证明协议构建针对数据库联接算子的保密计算协议。目前针对这两类基础安全方案的已知的效率最高的构建方法是利用格的极值问题及其复杂性。格的极值问题的模形式算法的结果为该种方法的安全性提供了保证。