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

《格的极值问题的模形式算法及应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文格的极值问题的模形式算法及应用研究ModularFormApproachtoSolvingExtremeLatticeProblemsandItsApplication学号：21117013大连理工大学DalianUniversityofTechnology大连理工大学学位论文独创性声明作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他己申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做

2、的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：作者签名：大连理工大学硕士学位论文摘要格问题在现在的公钥加密方案中扮演了相当重要的角色，格问题的计算难解性为许多创新性的公钥加密方案提供了理论依据。模形式算法作为新的随机算法解决欧几里得空间内的最短格向量(SVP)和最近格向量(CVP)问题。利用此方法，不仅可以求SVP和CVP的最小的格向量的非零2．范数的值，同时还可以求出满足要求的最小格向量的个数。模形式方法主要基于格向量的2．范数的母函数和西塔函数的特殊性质。从计算复杂性的观点来看，以解决

3、格向量问题的SVP问题为例，在所有以维度dim(An)=n阶hn=I(An)的整数格向量范围内，算法能够以(1一￡)的可能性找到最小的非零格向量同^，～、时计算出满足条件的最小非零格向量的个数，时间复杂度为(109log(n2hn))ut．n)log(1／￡)，空间复杂度为n的多项式复杂度。确切的说，影响时间复杂度最大的因素来源于模^，一、形式算法需要独立的随机抽取格向量(109log(n2hn))ut．nJlog(1／￡)次，其余的所有的操作对于算法复杂度的影响只是n的多项式复杂度。对于计算CVP问题时，情况相同。本文在阐述了格的模形式算法

4、及其复杂性后，以此为理论基础，运用匿名的公钥加密方案和零知识证明协议构建针对数据库联接算子的保密计算协议。目前针对这两类基础安全方案的已知的效率最高的构建方法是利用格的极值问题及其复杂性。格的极值问题的模形式算法的结果为该种方法的安全性提供了保证。关键词：格向量算法，SVP，CVP，模形式，西塔函数格的极值问题的模形式算法及应用研究ModularFormApproachtoSolvingExtremeLatticeProblemsandItsApplicationAbstractWeconstructnewrandomizedalgorith

5、mstofindtheexactsolutionstotheshortestandclosestvectorproblems(SVPandCVP)inEuclideannorm(1z)forintegrallattices．Notonlytheminimal12-normofnon．zerolatticevectorsinSVPandtheminimal12-distanceinCVP，butalsohowmanylatticevectorsreachthoseminimumsCanbesimultaneouslycomputedbythea

6、lgorithms．Suchfunction’SmodularpropertiesareexploitedtodevelopourSVPandCVPsolvers．IncomputationalcomplexityperspectiveandtakeOurSVPsolverasanexample．fortheintegrallatticefamily(An)ofdimensiondimAn=nandlevelhn=I(An)(theminimalpositiveintegersuchthattheduallattice锥scaledbyhl∥

7、isintegral)polynomialinn，thisalgorithmCanfindtheminimal12-normofnon．zerolatticevectorsandthenumberofsuchshortestvectorsinn、析tllsuccessprobability1一￡intheasymptoticspace-complexityofpolynomialinnandasymptotictime．complexityof(109log(nZhn))叭⋯log(1／￡)．Inaddition，theonlycontrib

8、utiontothealgorithm’Sexponentialtimecomplexity(109log(nZhn))叭叫log(1／￡)comesfromind