随着量子计算理论和量子计算机技术的迅速发展,传统公钥密码算法受到巨大挑战.可以抵抗量子计算机攻击的困难问题以及相关抗量子密码体制的分析与设计成为当前密码学和数学中的热点研究领域.在2019年初,NIST公布了第2轮26个抗量子密码算法标准征集的候选算法,其中有12个密码算法是基于格中困难问题所设计的.格密码的发展大体分为两条主线:一是从格中经典数学问题的研究发展到近30多年来高维格困难问题的求解算法及其计算复杂性理论研究;二是从使用格困难问题的求解算法分析非格公钥密码体制的安全性发展到基于格中困难问题设计抗量子密码体制.目前,格密码体制的设计主要基于下面三类困难问题:LWE(Learning with Errors)问题、SIS(Short Integer Solution)问题和NTRU(Number Theory Research Unit)问题.在本文中,我们主要考虑以下三类问题:1.环LWE问题与模LWE问题的困难性研究及归约;2.任意分圆域上基于NTRU的可证明安全的加密体制的设计;3.一般分圆域中的基于NTR.U的陷门构造及其应用.环LWE问题v.s.模LWE问题:为了更好地平衡安全性和实现效率,环LWE问题和模LWE问题分别被系统地研究.与经典欧式格上的LWE问题相比,环(模)LWE的worst-case的困难性归约更紧,并且基于模LWE问题和环LWE问题设计的密码体制在实现效率和存储空间上也有一定的优势.不过对应地,环(模)LWE问题的困难性假设比经典LWE问题要强一些.与理想格相比,模格的代数结构更无序,因此人们普遍认为模LWE问题应该要比类似参数的环LWE问题困难.目前唯一已知的详细讨论模LWE问题到环LWE问题的归约的结果是Albrecht等人在2017年亚密会上给出的.Albrecht等人采用模-维数转换的技巧,直接将Normal Form的模LWE问题的实例转换为环LWE问题的实例.然后,Albrecht等人在powers-of-2这一类特殊的分圆域中,使用系数嵌入分析了求解和判定版本问题对应的归约结果.值得注意的是,在模LWE对应的情况下,模-维数转换方法的输入和输出的统计距离难以控制.所以,Albrecht等人给出的判定版本的模LWE问题到环LWE问题的归约损失是指数大小的,并不能直接证明大模数的判定版本的环LWE问题比小模数的模LWE问题困难.同时,Albrecht等人也仅仅针对powers-of-2这一类特殊的分圆多项式环,采用系数嵌入分析了求解版本的Normal Form的模LWE问题与求解版本的环LWE问题之间的归约关系.模LWE问题到Normal Form的模LWE问题的归约并没有详细讨论.同时,Albrecht等人使用的归约方法对于求解版本的LWE问题的归约在一般的代数数域中(甚至一般的分圆域中)是否适用也仍需进一步讨论.在应用中,绝大多数密码体制所依赖的LWE问题都是判定版本的(如NIST 候选算法 KCL、CRYSTALS-KYBER、CRYSTALS-DILITHIUM、AKCN等),这就使得详细研究一般数域中的(判定版本的)模LWE问题和环LWE问题之间的区别与联系变得具有很大的理论意义和实用价值.在本文中,我们通过引入适当的中间问题,利用分圆域中存在的性质非常好的基(powerful基和decoding基)并综合使用模-维数转换技巧以及对偶攻击的思想,将任意分圆域K上的秩为d,计算模数为q的判定版本的模LWE问题归约到了计算模数为qd的判定版本的环LWE问题.具体来讲,我们的归约路线为:判定版本的模LWE问题→Normal Form的判定版本的模LWE问题→Normal Form的求解版本的模LWE问题→求解版本的环LWE问题→判定版本的环LWE问题.与直接将判定版本的模LWE问题归约到判定版本的环LWE问题相比,我们的归约的归约损失很小,对应的LWE问题的误差所服从的高斯分布的参数只增大了一些[K:Q]=n的小多项式倍.我们的归约结果的一个重要的推论是,我们可以将计算模数q≈O(n5.75),误差参数α≈O(n-4.25)的判定版本的模LWE问题归约到对应的误差参数Γ≈O(n-0.5)的判定版本的环LWE问题.结合已有的结论,我们就可以将渐进参数γ≈O(n5)的worst-case的模格中的基本困难问题(如SIVPγ)严格地归约到对应的判定版本的环LWE问题.同时,我们的分析结果表明,模-维数转换的方法在任意分圆域中均可以有效使用.我们也利用类似的思路给出了环LWE问题的自归约,这可以用来证明一大类非素数模数q对应的判定版本的环LWE问题的困难性.同时,我们也给出了任意分圆域中的判定版本的模LWE问题到一类模SIVPγ问题的反归约,从而建立了 worst-case的模格中的基本困难问题和一类average-case的模SIVPγ问题的联系.值得注意的是,对于一般的数域K,只要能找到其分式理想Rˇ的性质足够好的一组基,则我们的归约方法就可以推广到数域K中.可证明安全的NTRUEncrypt:基于NTRU的加密体制(NTRUEncrypt)最早是由 Hoffstein、Pipher 和 Silverman 在 1996 年提出的.早期的 NTRUEncrypt 入选了 IEEE的标准-IEEE P1363,是已知的运行速度最快的基于格的密码体制之一.由于其高效的运行效率、适中的密钥密文尺寸以及可以抵抗量子计算机攻击的特性,人们普遍地将NTRUEncrypt视为后量子时代公钥加密算法RSA和ECC的替代品之一.对早期的NTRUEncrypt的研究而引申出来的NTRU问题在密码学中也有着广泛的应用.很多基于NTRU的密码体制都具有设计简单、参数尺寸小、运行速度快等优点.基于NTRU问题设计的一些加密和密钥交换算法,如NTRU,NTRU Prime等,也入选了 NIST的候选算法进入了第2轮评估.但是,经典的NTRUEncrypt及其变种加密体制的安全性是启发式的.这一点与基于LWE的加密体制很不同.第一次将NTRUEncrypt的安全性与worst-case 的格中基本困难问题联系起来的工作是 Stehl e和 Steinfeld 在 2011 年欧密会中给出的.他们在powers-of-2这一类特殊的分圆多项式环中采用系数嵌入首次将NTRUEncrypt的IND-CPA安全性与相应的判定版本的(多项式)环LWE问题联系起来,进而综合已有的结论,证明了在适当参数选择下,NTRUEncrypt的IND-CPA安全性可以由这一类特殊的分圆域中worst-case的理想格中基本困难问题所保证.Stehle和Steinfeld提出的一个公开问题就是能否将他们的构造方法推广到一般的多项式环中.随后,喻洋等人分别将可证明安全的NTRUEncrypt推广到了 prime和prime-powers这些特殊的分圆多项式环上.考虑到现有攻击算法的攻击效率,目前设计格密码体制所用到的格的维数一般不小于512维.无论是prime还是prime-powers的分圆域,达到这个维数要求的分圆域均有比较多的子域.考虑到子域攻击,这些特殊的分圆域上对应的基本格中困难问题的计算复杂度可能比更一般的分圆域要低.相应地,在这些特殊的分圆域上设计的密码体制的安全性可能有隐患.在本文中,我们严格证明了在任意的分圆域中,在适当参数选择下,服从适当离散高斯分布的NTRUEncrypt的私钥f,g生成的公钥h=g·f-1与环Rq×上的均匀分布统计不可区分.进而利用分圆域的性质比较好的基(powerful基和decoding基)并引入基-系数嵌入,采用canonical嵌入在任意的分圆域上设计了可证明IND-CPA安全的NTRUEncrypt.我们的加密体制的IND-CPA安全性依赖于对应分圆域上的判定版本的环LWE问题.结合已知的结论,可以证明我们的NTRUEncrypt的IND-CPA安全性可以由对应分圆域中worst-case的理想格中的基本困难问题(如SIVPγ)所保证.同时,在任意取定的分圆域中,与现在已有的可证明安全的NTRUEncrypt相比,我们的NTRUEncrypt的计算模数q和最后安全性所依赖的基本格中困难问题的渐进参数γ对明文空间的依赖更小.这就使得在相似的(甚至比前人更弱的)安全性假设条件下,我们的NTRUEncrypt的参数选择更灵活,密码体制的实现效率更高.同时,我们的加密体制的解密错误率也比前人的低的多.我们还给出了任意分圆域中dual环LWE问题到primal环LWE问题的归约损失非常小的归约.基于NTRU的陷门构造:早期的应用比较广泛的基于格的陷门函数的构造是Gentry等人给出的.Gentry等人使用改进的最近平面算法给出了利用随机格的一组短基来进行有效的离散高斯取样的方法.结合已有的生成随机格以及相应格中短基的方法,Gentry等人在经典欧式格中构造了一类抗碰撞的陷门原像取样函数并给出了一系列应用(如设计了格中具有worst-case困难性保证的可证明安全的签名和基于身份的加密体制).经典欧式格中的这些设计可以采用系数嵌入较为平凡地推广到理想格中.但是相应的,这样的推广没有有效地利用多项式环的代数结构,一般会造成构造的密码原语具有参数尺寸太大、实现效率不高等缺点.本质上讲,Gentry等人改进了已有的利用随机格的陷门短基的方法,并给出了新密码学原语的构造以及相关应用.基于NTRU的签名体制(如NTRUSign)的私钥即为NTRU格的一组短基.在多项式环中结合Gentry等人提出的方法与NTRUSign的设计思路应该可以将Gentry等人的设计思路有效地推广到理想格中.最早注意到这一点的是Stehle和Steinfeld.他们首次在powers-of-2这一类特殊的分圆多项式环中采用系数嵌入基于NTRU问题给出了抗碰撞的原像取样函数的构造,并基于此函数采用Hash-and-Sign的方法在随机预示模型下给出了第一个具有worst-case困难性保证的基于NTRU的签名体制.这也是第一个基于NTRU问题的可证明安全的签名体制.但是,类似于可证明安全的NTRUEncrypt的情况,将密码体制的设计限制在powers-of-2这一类特殊的分圆多项式环中会使得相关体制的设计更加受限.同时,这种环上设计的密码体制可能有潜在的安全隐患.能否在一般的多项式环设计可证明安全的基于NTRU的签名体制也是Stehle和Steinfeld在文章中提出的一个公开问题.在本文中,我们采用canonical嵌入讨论了在一般的分圆域上设计安全的抗碰撞的原像取样函数的方法.在一大类分圆域中,对于适当的参数选择,我们给出了 Dedekind Zeta函数在2处取值的上界估计,由此进一步严格证明了改进的传统NTRUSign的密钥生成算法(也是我们构造的抗碰撞的原像取样算法的密钥生成算法)是概率多项式时间的.我们也改进了我们早期结果中的部分结论,并证明了任意分圆域中的一类非齐次的环ISIS问题的困难性.随后我们采用现有的构造方法,利用分圆域的性质非常好的基(powerful基和decoding基)进行离散高斯取样,在一大类分圆域中设计了(claw-free)抗碰撞的原像取样函数,并对在一般的分圆域中的构造进行了讨论.基于我们设计的抗碰撞的原像取样函数,综合使用Hash-and-Sign构造方法和拒绝采样技术,我们还在一般的分圆域中讨论了基于NTRU问题的具有worst-case困难性保证的签名体制、基于身份的加密体制以及基于身份的签名体制等密码原语的构造.