格密码学基础（一）：前言

通往NIST标准之路

现代格密码学的起源可以追溯到1990年代中期的两项工作。第一项是Ajtai的成果[Ajt96],该成果表明能够求解小整数解(SIS)问题的一个随机实例,其难度等同于求解 所有 格上某些被认为是困难的问题。第二项是NTRU [HPS98],这是一个基于多项式环上新的、潜在困难的格问题的高效公钥密码系统。Ajtai[Ajt96]的工作同时也启发了一个具有类似强安全保证的加密方案[AD97],但不幸的是其实例化完全不实用。另一方面,NTRU密码系统虽然非常实用,但缺乏理论基础。事实上,有各种基于NTRU方法的构造[GGH97, Sil01, HPS01, HHGP03],或使用其他技巧来提高效率的构造,后来被证明是弱化的或完全不安全的[Ngu99, Gen01, GS02, NR06]。

格密码学研究的理论和实践两条线索在接下来的十年中交织在一起。Micciancio、Peikert、Regev、Lyubashevsky和Micciancio[Mic02, PR06, LM06]等人的工作提炼出了代数结构,使得基于格的原语既能拥有NTRU的效率,又能享有与Ajtai原始构造相同类型的理论保证。

或者通过利用允许数论变换[LMPR08]的多项式环获得更好的效率——特别是环 $\mathbb{Z}_q[X]/(X^{2^k}+1)$,该环现在在包括三个NIST格标准在内的实用格构造中无处不在。一个有趣的旁注是,加速NTRU的一个早期建议是使用支持数论变换(NTT)的多项式环。但在一次利用所提议环的结构的攻击[Gen01]之后,建议是不要使用允许NTT的环[Sil01],因为必要的结构看起来与[Gen01]中被利用的结构相似。

然而,[PR06, LM06]的理论结果精确地说明了代数环需要具有什么性质才能与最坏情况格问题建立联系(被[Gen01]攻击的环不具有必要的性质),并且不排除使用支持NTT的环。我们可以将这一事件视为理论工作提高实用方案效率的一个很好的例子。

❝

特别地,研究表明,求解多项式环上SIS问题的随机实例的难度等同于在具有某些相关代数结构的格中求解最坏情况格问题。

与此同时,Regev引入了非常通用的带错误学习(LWE)问题[Reg05],这极大地扩展了可能的基于格的原语的范围。在那项工作中,Regev还证明了求解LWE的随机实例的难度等同于(量子地，量子要求后来在[Pei09]中被移除。)求解与[Ajt96]中相同的最坏情况格问题。结合对格问题具体难度的更好理解[GN08],研究人员能够创建基于坚实理论基础的高效(至少在渐近意义上)加密、签名和基于身份的加密方案[Reg05, LM08, GPV08, Lyu09, SSTX09, LPR10]。

由于首次实现了基于任何假设的全同态加密方案[Gen09],以及针对构建能够破解所有基于因数分解和离散对数的密码学的量子计算机的研究迅速增加[Sho97],格密码学在2010年代初获得了进一步的进展势头。在2010年代中期,各种改进和增强(例如[GLP12, BG14, DLP14, LS15, DP16, ADPS16])使得格构造从仅仅是渐近高效发展到具有真正实用的实例化。到2017年NIST后量子密码标准化进程启动时[NIS17],基于格的方案已经成为最快速、最紧凑的抗量子原语之一,甚至在原始性能方面超越了其基于数论的对应方案。

本教程的范围

本教程专注于描述NIST标准化并纳入CNSA 2.0算法套件[Age24]的两个"主要"格方案中使用的基本数学概念和设计决策。它们是密钥封装机制/加密方案CRYSTALS-Kyber(ML-KEM)[BDK+18, NIS24b]和签名方案CRYSTALS-Dilithium(ML-DSA)[DKL+18, NIS24a]。此外,我们还将介绍其他基于格的密钥封装机制(如Frodo和NTRU [HPS98])背后的主要思想,这些方案的版本也被提交到了NIST标准化进程。

本教程的目标读者是那些已经熟悉基本公钥密码学以及使用归约论证证明密码方案安全性思想的人。因此假设读者对不可区分性、混合论证、选择明文攻击(CPA)安全加密、随机预言机、Fiat-Shamir变换等概念并不陌生。熟悉这些概念的人很可能首次接触它们是在学习基于离散对数或RSA问题难度的公钥密码原语时。记住离散对数构造,如ElGamal加密和Schnorr签名,实际上对理解格构造的高层思想会非常有用。

许多人观察到,基于因数分解或离散对数的经典密码学与格密码学之间的一个区别是,格密码学是"混乱的"。不是从一个参数推导出安全性,而是有几个参数以各种方式影响安全性。还有许多优化技巧涉及诸如丢弃一些低阶比特、舍入等技术,这使得方案看起来更加复杂。从积极的方面来看,许多格构造需要很少"深奥"的数学概念——从头理解和实现Kyber和Dilithium所需的数学背景比许多椭圆曲线构造要少。

❝

这并不是说格密码学中没有数学。密码分析需要来自代数几何和代数数论的相当深入的概念，即使是理解涉及陷门采样的构造（比如FALCON [PFH+17]数字签名方案）也需要一些相当非平凡的数论知识。但本教程中不需要这些知识，因为本教程只关注Kyber和Dilithium所需的数学。

习惯格构造所带来的问题需要一点练习和耐心,因此鼓励读者带着纸笔通读本教程,算出细节并适应这种混乱。不要担心在算出混乱的细节后,它们几乎立即就被你忘记了。重要的是理解高层概念;然后知道你曾经能够算出混乱的细节,这意味着如果必要的话你应该能够重复这个过程。

本教程没有涵盖很多关于格的内容。例如,它没有涉及超越加密或签名的更"高级"的构造,关于其中一些的良好概述可以在[Pei16]中找到。它也没有过多讨论精确的密码分析或格密码学的几何方面,这些对于理解一些更高级的构造至关重要。关于格的几何基础的良好参考是[MG02]和讲义[Mic19]。一些与NIST标准化候选方案所基于的问题的算法和密码分析相关的最新论文包括[ACD+18, AM18, ADH+19, DP23]。值得注意的是,还缺少NIST选择标准化的另一个基于格的签名方案FALCON,理解它需要更深入地研究格的几何,可以从研究[GPV08, Pei10, MP12]的开创性工作开始,这些工作解释了如何创建在许多格构造中无处不在的基于格的陷门采样算法,然后理解这些技术如何针对FALCON的具体实例化进行优化[DLP14, DP16, PP19]。

虽然对基于格的加密和签名感兴趣的主要原因是它们假定的抗量子攻击能力,但我们不涉及这个话题。随机预言机模型(ROM),在其中安全证明里,具体的密码哈希函数被替换为一个完美的随机函数,敌手只能通过预言机访问该函数,在量子设置中有一个类似物(QROM),其中允许敌手对这样的函数进行量子查询(即在输入的叠加态上查询预言机)。虽然ROM中的安全证明不会立即延续到QROM设置,但最近有许多工作将两者拉得更近(例如[HHK17, SXY18, KLS18, DFMS19, LZ19, JMW24]),唯一剩下的区别是安全归约的紧密性或其中使用的具体参数。在撰写本文时,如果只是将所有密码函数替换为具有必要量子安全性的对应函数,那么如果给敌手额外的量子能力在输入的叠加态上查询随机预言机,对于在ROM中被证明安全的实际方案,目前没有已知的改进攻击。

大纲

本教程不采用展示Kyber和Dilithium的最短路径;而是绕一些弯路以便涉及在许多格密码学中使用的相关主题。在第2节中,我们展示了基于LWE问题难度的环上基于格的加密框架,该框架源于Regev[Reg09]的原始工作,以及来自[PVW08, ACPS09, LPS10, LPR10, LP11]等工作的一些变化和优化。我们还讨论了许多压缩密文的小但关键的技巧。其中一些技巧相当通用,在后面章节介绍的构造中也会派上用场。在第3节中,我们将格引入为几何对象,并描述LWE和SIS问题与求解格问题难度之间的联系。在第4节中,我们回顾多项式环,并实例化第2节中加密方案的类似版本,这得到了Kyber(ML-KEM)加密方案。在该节中,我们还描述了加速某些特定多项式环上运算的数论变换算法。最后在第5节中,我们展示了构造Schnorr签名方案的优化格类似物所需的所有技术,Dilithium(ML-DSA)[DKL+18]就是其中的一个例子。该方案是通过将Fiat-Shamir变换应用于基于格的$\Sigma$-协议而构建的。后者也作为理解更高级的基于格的构造(如零知识证明)的门户。

参考文献

[ABD16] Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. In CRYPTO (1), volume 9814 of Lecture Notes in Computer Science, pages 153-178. Springer, 2016.

[ABD+17] Erdem Alkim, Joppe W. Bos, Léo Ducas, Karen Easterbrook, Brian LaMacchia, Patrick Longa, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Chris Peikert, Ananth Raghunathan, and Douglas Stebila. FrodoKEM: Learning with errors key encapsulation, 2017.

[ACD+18] Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. Estimate all the {LWE, NTRU} schemes! In SCN, volume 11035 of Lecture Notes in Computer Science, pages 351-367. Springer, 2018.

[ACPS09] Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In CRYPTO, pages 595-618, 2009.

[AD97] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC, pages 284-293, 1997.

[ADH+19] Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In EUROCRYPT (2), volume 11477 of Lecture Notes in Computer Science, pages 717-746. Springer, 2019.

[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - A new hope. In USENIX Security Symposium, pages 327-343. USENIX Association, 2016.

[ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2^n time using discrete gaussian sampling: Extended abstract. In STOC, pages 733-742. ACM, 2015.

[AG11] Sanjeev Arora and Rong Ge. New algorithms for learning in presence of errors. In ICALP (1), pages 403-415, 2011.

[Age24] National Security Agency. The commercial national security algorithm suite 2.0 and quantum computing faq. Technical report, 2024.

[AGV09] Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, volume 5444 of Lecture Notes in Computer Science, pages 474-495. Springer, 2009.

[Ajt96] Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99-108, 1996.

[AKPW13] Joël Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited - new reduction, properties and applications. In CRYPTO (1), volume 8042 of Lecture Notes in Computer Science, pages 57-74. Springer, 2013.

[AKS01] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In STOC, pages 601-610. ACM, 2001.

[AM18] Divesh Aggarwal and Priyanka Mukhopadhyay. Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm. In ISAAC, volume 123 of LIPIcs, pages 35:1-35:13. Schloss Dagstuhl, 2018.

[APS15] Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. J. Math. Cryptol., 9(3):169-203, 2015.

[AS18] Divesh Aggarwal and Noah Stephens-Davidowitz. Just take the average! an embarrassingly simple 2^n-time algorithm for SVP (and CVP). In SOSA@SODA, volume 61 of OASICS, pages 12:1-12:19. Schloss Dagstuhl, 2018.

[BCD+16] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the ring! practical, quantum-secure key exchange from LWE. In ACM Conference on Computer and Communications Security, pages 1006-1018. ACM, 2016.

[BDK+18] Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In 2018 IEEE European Symposium on Security and Privacy, pages 353-367, 2018.

[BDL24] Amit Berman, Ariel Doubchak, and Noam Livne. A note on the hint in the dilithium digital signature scheme. Cryptology ePrint Archive, Paper 2024/1660, 2024.

[BG14] Shi Bai and Steven D. Galbraith. An improved compression technique for signatures based on learning with errors. In CT-RSA, pages 28-47, 2014.

[BGM+16] Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. On the hardness of learning with rounding over small modulus. In TCC (A1), volume 9562 of Lecture Notes in Computer Science, pages 209-224. Springer, 2016.

[BP02] Mihir Bellare and Adriana Palacio. GQ and schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 162-177. Springer, 2002.

[BPR12] Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In EUROCRYPT, volume 7237 of Lecture Notes in Computer Science, pages 719-737. Springer, 2012.

[BS16] Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In SODA, pages 893-902. SIAM, 2016.

[BV11] Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-lwe and security for key dependent messages. In CRYPTO, pages 505-524, 2011.

[CDH+17] Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas Hülsing, Joost Rijneveld, Tsunekazu Saito, John M. Schank, Peter Schwabe, William Whyte, Keita Xagawa, Takashi Yamakawa, and Zhenfei Zhang. NTRU, 2017.

[CDPR16] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. In EUROCRYPT (2), volume 9666 of Lecture Notes in Computer Science, pages 559-585. Springer, 2016.

[CDW17] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger class relations and application to ideal-SVP. In EUROCRYPT (1), volume 10210 of Lecture Notes in Computer Science, pages 324-348, 2017.

[CGS14] Peter Campbell, Michael Groves, and Dan Shepherd. Soliloquy: A cautionary tale. Technical report, ETSI 2nd Quantum-Safe Crypto Workshop, 2014.

[CHK+21] Chi-Ming Marvin Chung, Vincent Hwang, Matthias J. Kannwischer, Gregor Seiler, Cheng-Jhih Shih, and Bo-Yin Yang. NTT multiplication for ntt-unfriendly rings new speed records for saber and NTRU on cortex-m4 and AVX2. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(2):159-188, 2021.

[CJL16] Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. An algorithm for ntru problems and cryptanalysis of the ggh multilinear map without a low-level encoding of zero. LMS Journal of Computation and Mathematics, 19(A):255-266, 2016.

[DDLL13] Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40-56, 2013.

[Den02] Alexander W. Dent. A designer's guide to kems. IACR Cryptology ePrint Archive, 2002.

[DFMS19] Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner. Security of the fiat-shamir transformation in the quantum random-oracle model. In CRYPTO (2), volume 11693 of Lecture Notes in Computer Science, pages 356-383. Springer, 2019.

[DFPS22] Julien Devevey, Omar Fawzi, Alain Passelègue, and Damien Stehlé. On rejection sampling in lyubashevsky's signature scheme. In ASIACRYPT (4), volume 13794 of Lecture Notes in Computer Science, pages 34-64. Springer, 2022.

[DKL+18] Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(1):238-268, 2018.

[DLP14] Léo Ducas, Vadim Lyubashevsky, and Thomas Prest. Efficient identity-based encryption over NTRU lattices. In ASIACRYPT, pages 22-41, 2014.

[DM13] Nico Döttling and Jörn Müller-Quade. Lossy codes and a new variant of the learning-with-errors problem. In EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 18-34. Springer, 2013.

[DP16] Léo Ducas and Thomas Prest. Fast fourier orthogonalization. In ISSAC, pages 191-198, 2016.

[DP23] Léo Ducas and Ludo N. Pulles. Does the dual-sieve attack on learning with errors even work? In CRYPTO (3), volume 14083 of Lecture Notes in Computer Science, pages 37-69. Springer, 2023.

[FO99] Eiichiro Fujisaki and Tatsuaki Okamoto. Secure integration of asymmetric and symmetric encryption schemes. In CRYPTO, pages 537-554, 1999.

[GdKQ+24] Phillip Gajland, Bor de Kock, Miguel Quaresma, Giulio Malavolta, and Peter Schwabe. SWOOSH: efficient lattice-based non-interactive key exchange. In USENIX Security Symposium. USENIX Association, 2024.

[Gen01] Craig Gentry. Key recovery and message attacks on ntru-composite. In EUROCRYPT, volume 2045 of Lecture Notes in Computer Science, pages 182-194. Springer, 2001.

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In STOC, pages 169-178, 2009.

[GGH97] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO, pages 112-131, 1997.

[GKRS22] Siyao Guo, Pritish Kamath, Alon Rosen, and Katerina Sotiraki. Limits on the efficiency of (ring) lwe-based non-interactive key exchange. J. Cryptol., 35(1):1, 2022.

[GLP12] Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems. In CHES, pages 530-547, 2012.

[GN08] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In EUROCRYPT, pages 31-51, 2008.

[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197-206, 2008.

[GS02] Craig Gentry and Michael Szydlo. Cryptanalysis of the revised ntru signature scheme. In EUROCRYPT, pages 299-320, 2002.

[HHGP+03] Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, and William Whyte. Ntrusign: Digital signatures using the ntru lattice. In CT-RSA, pages 122-140, 2003.

[HHK17] Dennis Hofheinz, Kathrin Hövelmanns, and Eike Kiltz. A modular analysis of the fujisaki-okamoto transformation. In TCC, pages 341-371, 2017.

[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: A ring-based public key cryptosystem. In ANTS, pages 267-288, 1998.

[HPS01] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NSS: An NTRU lattice-based signature scheme. In EUROCRYPT, pages 211-228, 2001.

[IN96] Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199-216, 1996.

[IZ89] Russell Impagliazzo and David Zuckerman. How to recycle random bits. In FOCS, pages 248-253. IEEE Computer Society, 1989.

[JMW24] Kelsey A. Jackson, Carl A. Miller, and Daochen Wang. Evaluating the security of crystals-dilithium in the quantum random oracle model. In EUROCRYPT (6), volume 14656 of Lecture Notes in Computer Science, pages 418-446. Springer, 2024.

[KF17] Paul Kirchner and Pierre-Alain Fouque. Revisiting lattice attacks on overstretched NTRU parameters. In EUROCRYPT (1), volume 10210 of Lecture Notes in Computer Science, pages 3-26, 2017.

[KLS18] Eike Kiltz, Vadim Lyubashevsky, and Christian Schaffner. A concrete treatment of fiat-shamir signatures in the quantum random-oracle model. In EUROCRYPT (3), volume 10822 of Lecture Notes in Computer Science, pages 552-586. Springer, 2018.

[KW03] Jonathan Katz and Nan Wang. Efficiency improvements for signature schemes with tight security reductions. In CCS, pages 155-164. ACM, 2003.

[LLL82] Arjen Lenstra, Hendrik Lenstra Jr., and Laszlo Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen, (261):513-534, 1982.

[LM06] Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144-155, 2006.

[LM08] Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-based digital signatures. In TCC, pages 37-54, 2008.

[LM18] Vadim Lyubashevsky and Daniele Micciancio. Asymptotically efficient lattice-based digital signatures. J. Cryptol., 31(3):774-797, 2018.

[LM21] Baiyu Li and Daniele Micciancio. On the security of homomorphic encryption on approximate numbers. In EUROCRYPT (1), volume 12696 of Lecture Notes in Computer Science, pages 648-677. Springer, 2021.

[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen. SWIFFT: A modest proposal for FFT hashing. In FSE, pages 54-72, 2008.

[LP11] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for lwe-based encryption. In CT-RSA, pages 319-339, 2011.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT, pages 1-23, 2010.

[LPR13a] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. J. ACM, 60(6):43, 2013.

[LPR13b] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. A toolkit for ring-lwe cryptography. In EUROCRYPT, pages 35-54, 2013.

[LPS10] Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. Public-key cryptographic primitives provably as secure as subset sum. In TCC, pages 382-400, 2010.

[LS15] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Des. Codes Cryptography, 75(3):565-599, 2015.

[LS18] Vadim Lyubashevsky and Gregor Seiler. Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs. In EUROCRYPT (1), volume 10820 of Lecture Notes in Computer Science, pages 204-224. Springer, 2018. [LS19] Vadim Lyubashevsky and Gregor Seiler. NTTRU: truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(3):180-201, 2019.

[Lyu09] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In ASIACRYPT, pages 598-616, 2009.

[Lyu12] Vadim Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, pages 738-755, 2012.

[LZ19] Qipeng Liu and Mark Zhandry. Revisiting post-quantum fiat-shamir. In CRYPTO (2), volume 11693 of Lecture Notes in Computer Science, pages 326-355. Springer, 2019.

[MG02] Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems - a cryptograhic perspective, volume 671 of The Kluwer international series in engineering and computer science. Springer, 2002.

[Mic02] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In FOCS, pages 356-365. IEEE Computer Society, 2002.

[Mic07] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365-411, 2007.

[Mic19] Daniele Micciancio. Lattices: Algorithms and applications, 2019.

[MP12] Daniele Micciancio and Chris Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In EUROCRYPT, pages 700-718, 2012.

[MP13] Daniele Micciancio and Chris Peikert. Hardness of sis and lwe with small parameters. In CRYPTO (1), pages 21-39, 2013.

[MR07] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267-302, 2007.

[MR09] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-quantum Cryptography, pages 147-191. Springer, 2009.

[Ngu99] Phong Q. Nguyen. Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97. In CRYPTO, pages 288-304, 1999.

[NIS17] NIST. Post-quantum cryptography. Technical report, 2017.

[NIS24a] NIST. Module-lattice-based digital signature standard. Technical report, 2024.

[NIS24b] NIST. Module-lattice-based key-encapsulation mechanism standard. Technical report, 2024.

[NR06] Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. In EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 271-288. Springer, 2006.

[NR09] Phong Q. Nguyen and Oded Regev. Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures. J. Cryptology, 22(2):139-160, 2009.

[Oka92] Tatsuaki Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In CRYPTO, volume 740 of Lecture Notes in Computer Science, pages 31-53. Springer, 1992.

[Pei09] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In STOC, pages 333-342, 2009.

[Pei10] Chris Peikert. An efficient and parallel gaussian sampler for lattices. In CRYPTO, pages 80-97, 2010.

[Pei16] Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283-424, 2016.

[PFH+17] Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. FALCON. Technical report, National Institute of Standards and Technology, 2017.

[PP19] Thomas Pornin and Thomas Prest. More efficient algorithms for the NTRU key generation using the field norm. In Public Key Cryptography (2), volume 11443 of Lecture Notes in Computer Science, pages 504-533. Springer, 2019.

[PR06] Chris Peikert and Alon Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pages 145-166, 2006.

[PRS17] Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandomness of ring-lwe for any ring and modulus. In STOC, pages 461-473. ACM, 2017.

[PVW08] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, volume 5157 of Lecture Notes in Computer Science, pages 554-571. Springer, 2008.

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84-93. ACM, 2005.

[Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009.

[Sch89] Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In CRYPTO, pages 239-252, 1989.

[Sho97] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484-1509, 1997.

[Sil01] Joseph Silverman. Wraps, gaps, and lattice constants. Technical report, NTRU Cryptosystems, 2001.

[SS11] Damien Stehlé and Ron Steinfeld. Making NTRU as secure as worst-case problems over ideal lattices. In EUROCRYPT, pages 27-47, 2011.

[SSTX09] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In ASIACRYPT, pages 617-635, 2009.

[SXY18] Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa. Tightly-secure key-encapsulation mechanism in the quantum random oracle model. In EUROCRYPT (3), volume 10822 of Lecture Notes in Computer Science, pages 520-551. Springer, 2018.

[ZYF+20] Jiang Zhang, Yu Yu, Shuqin Fan, Zhenfeng Zhang, and Kang Yang. Tweaking the asymmetry of asymmetric-key cryptography on lattices: Kems and signatures of smaller sizes. In Public Key Cryptography (2), volume 12111 of Lecture Notes in Computer Science, pages 37-65. Springer, 2020.

备战后量子：格密码学初学者指南

• 本文转载自： mp.weixin.qq.com/s/7Dtdr... , 如有侵权请联系管理员删除。