格密码学研究

密码学报ISSN2095-7025CN10-1195/TNE-mail:[e-mail]search,2014,1(1):13–27©《密码学报》编辑部版权所有.Tel/Fax:[phone]格密码学研究王小云1,刘明洁21.清华大学高等研究院,北京1000842.北京大学北京国际数学研究中心,北京100871通讯作者:王小云,E-mail:[e-mail]摘要:格密码是一类备受关注的抗量子计算攻击的公钥密码体制.格密码理论的研究涉及的密码数学问题很多,学科交叉特色明显,研究方法趋于多元化.格密码的发展大体分为两条主线:一是从具有悠久历史的格经典数学问题的研究发展到近30多年来高维格困难问题的求解算法及其计算复杂性理论研究;二是从使用格困难问题的求解算法分析非格公钥密码体制的安全性发展到基于格困难问题的密码体制的设计.本文从格困难问题的计算复杂性研究、格困难问题的求解算法、格密码体制的设计以及格密码分析四个方面较为全面地回顾了格密码领域30多年来的主要研究成果,并试图体现四个研究领域方法的渗透与融合.此外,对与格密码理论研究有重要影响的一些格数学问题的经典研究方法与成果本文也进行了简单的描述.关键词:格理论;密码分析;格密码体制;格困难问题;计算复杂性中图法分类号:TP309.7文献标识码:A中文引用格式:王小云,刘明洁.格密码学研究[J].密码学报,2014,1(1):13–27.英文引用格式:WangXY,LiuMJ.Surveyoflattice-basedcryptography[J].JournalofCryptologicResearch,2014,1(1):13–27.SurveyofLattice-basedCryptographyWANGXiao-Yun1,LIUMing-Jie21.InstituteforAdvancedStudy,TsinghuaUniversity,Beijing100084,China2.BeijingInternationalCenterforMathematicalResearch,PekingUniversity,Beijing100871,ChinaCorrespondingauthor:WANGXiao-Yun,E-mail:[e-mail]:Lattice-basedcryptographyiswidelybelievedtoresistquantumcomputerattacks,whichinvolvesmanycryptographicmathematicalproblemsandbelongstointerdisciplinarystudy.Thedevelopmentoflattice-basedcryptographyfollowstwomainlines:Oneistostudythecomputationalcomplexityandsearchingalgorithmsforsolvinghardproblemsinhighdimensionallatticesbasedontheresearchofclassicallatticeproblems.Theotheristoanalyzethesecurityofnon-lattice-basedpublic-keycryptosystemsusingthealgorithmssolvinghardlatticeproblems,andfurthertodesignthelattice-basedcryptosystems.Thispapergivesasurveyofthemainprogressonlattice-basedcryptographyinrecent30years,whichcoversthefollowingconcerns:computationalcomplexityandsearchingalgorithmsrelatingtohardlatticeproblems,designandcryptanalysisoflattice-basedcryptosystems.Thepapertriestoreflecttherelationshipofthesefourareas.Inaddition,someclassicallatticeproblemsandrelativeimportantresultsaredescribed.基金项目:国家自然科学基金重点项目(61133013);国家重点基础研究发展计划(973计划)(2013CB834205)收稿日期:2013-12-15定稿日期:2014-01-04DOI:10.13868/j.cnki.jcr.00000214JournalofCryptologicResearch密码学报Vol.1,No.1,Feb.2014Keywords:latticetheory;cryptanalysis;lattice-basedcryptosystem;hardlatticeproblems;computationalcomplexity1前言格理论的研究源于1611年开普勒提出的如下猜想:在一个容器中堆放等半径的小球所能达到的昀大密度是18.1840年前后,高斯引进了格的概念并证明:在三维空间堆球,如果所有的球心构成一个格,那么堆积密度所能达到的昀大值是18.在过去的一个半世纪中,Minkowski、Hermite、Bourgain、Hlawka、Kabatyansky、Levenstein、Lovasz、Mahler、Rogers等著名数学家系统地发展了一般几何体的格堆积与覆盖理论.在这一发展过程中,确定一个给定几何体的昀大格堆积密度和昀小格覆盖密度一直是这一学科的核心问题.格是mR中一类具有周期性结构离散点的集合.严格地说,格是m维欧式空间mR的nmn个线性无关向量组12,,,nbbb的所有整系数线性组合,即1:,1,,niiiixxZinLBb向量组12,,,nbbb称为格的一组基.同一个格可以用不同的格基表示.m称为格的维数,n称为格的秩.满足mn的格称为满秩的.通常我们只考虑满秩的格.下面我们介绍格理论中一些基本概念和困难问题.格的行列式:格的行列式det()L的值定义为格基本体1,01iniiixxBb的体积,容易证明有TdetvolLBBB,其中B是以格基为列向量构成的矩阵.对偶格:对偶格与原格在同一个线性空间mR中,定义为*,,,mRZLxvLxv.逐次昀小长度:第i个逐次昀小长度i,定义为以原点为球心,包含i个线性无关格向量的昀小球的半径,即infdimspan,1,,inrriinLLB.昀短向量问题(ShortestVectorProblem,SVP):给定格L,找一个非零格向量v,满足对任意非零向量,uLvu.-近似昀短向量问题(SVP-):给定格L,找一个非零格向量v,满足对任意非零向量,uLvu.逐次昀小长度问题(SuccessiveMinimaProblem,SMP):给定一个秩为n的格L,找n个线性无关的向量is,满足,1,,iiniLs.昀短线性无关向量问题(ShortestIndependentVectorProblem,SIVP):给定一个秩为n的格L,找n个线性无关的格向量is满足,1,,ininsL.唯一昀短向量问题(UniqueShortestVectorProblem,uSVP-):给定格L,满足21LL,找该格的昀短向量.昀近向量问题(ClosestVectorProblem,CVP):给定一个格L和目标向量mRt,找一个非零格向量v,满足对任意非零向量,uLvtut.王小云等:格密码学研究综述15有界距离解码问题(BoundedDistanceDecoding,BDD-):给定一个格L,目标向量t满足1dist,tLL,找一个非零格向量v,满足对任意非零向量,uLvtut.判定版本-近似昀短向量问题(GapSVP-):给定格L和一个有理数r,如果1rL,则返回“是”;如果1rL,则返回“否”.其他情况随机返回“是”或“否”.堆积半径:对n维格,以格点为球心,r为半径做n维球,使得球两两不相交,昀大的r称作堆积半径.事实上这里12rL.覆盖半径:对n维格,以格点为球心,r为半径做n维球,能覆盖整个空间的昀小r称作覆盖半径.事实上,确定球的昀大格堆积密度等价于求格的昀短向量(SVP)的长度,确定球的昀小格覆盖密度则等价于求到格点的昀近距离(CVP).因此格中困难问题既是经典数论也是计算复杂性理论的重要研究课题.近30年来,在格中困难问题的复杂性与求解算法方面,国际上取得了许多重要成果.随着对格困难问题算法研究的深入,研究人员发现格理论在密码分析与设计中都有很广泛的应用.基于格的密码体制的安全性依赖于格中困难问题的难解程度,格中很多困难问题被证明是NP困难的,因此这类体制被普遍认为具有抗量子攻击的特性.本文主要描述格的困难问题的计算复杂性研究,格困难问题的求解算法以及基于格的密码分析与设计.本文剩余的内容安排如下:第二章主要介绍格中计算问题困难性研究的主要成果,第三章就格中困难问题的搜索算法展开论述,第四章讨论了格中困难问题的算法在公钥密码分析中的几个重要成果,第五章针对基于格的密码体制的设计的主要成果做了回顾,昀后在第六章中给出总结.2格中计算问题的困难性格中昀短向量问题是数论中的经典问题,1850年,Hermite证明了对于任意一个n维格昀短向量的长度小于detnL,其中n是Hermite常数.1905年Minkowski证明了22nneOnne[1,2].1978年Kabatyanskii和Levenshtein将n的上界改进到1.7442ne[3].这些结果给出了昀短向量长度的一个上界,为密码学家在该问题的研究提供了重要的参考.1981年,VanEmdeBoas[4]就证明了l范数下的精确SVP问题是NP-hard的,并猜测2l范数下SVP同样是NP-hard的.直到1998年,Ajtai[5]证明了2l范数下近似因子小于112n的昀短向量问题在随机归约下是NP-Hard的,即不存在有效的多项式算法求解近似因子为112n的SVP问题.随后Cai与Nerurkar[6]将SVP在随机归约下NP-hard的近似因子提高到11n.Miccinacio[7]考虑了一般范数度量下的昀短向量问题,基于一个数论猜想将(1)plp下SVP-问题的NP-hard因子提高到γ2.2005年,Khot[8]指出在随机归约下任意常数近似因子的SVP-是NP-hard的,并且在更强的复杂性假设polylogNPRTIME2n下SVP-(1/2logγ2n)是NP-hard,在同样假设下,Haviv与Regev利用基于张量积的格构造归约技术又将近似因子提高到1logγ2n.进一步,若NPRSUBEXP,则NP-hard因子可达到loglogcnn,其中0c为一常数.对1l和l范数的SVP问题目前昀好的结果分别是被证明在近似因子小于2[7]和loglogcnn[9]时,相应的近似SVP是NP-hard的.到目前为止,具有NP-hard困难性的SVP问题不仅被广泛地用于格密码体制的设计,其快速求解算法也