邁向實際的格密碼學

Towards Practical Lattice-based Cryptography

郭博鈞(Po-Chun Kuo)

指導教授 ： 鄭振牟

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2020年)

https://doi.org/10.6342/NTU202000678

摘要

在近年，量子電腦的技術蓬勃發展，其潛在計算能力威脅了古典密碼學的系統安全性；因此，後量子密碼學應運而生，旨在發展可抵抗量子電腦攻擊的密碼系統。格密碼學是後量子密碼學中最有潛力的一個子領域，而本論文探討格密碼系統的中兩個最重要的面向：安全與效率。對於一個格密碼系統，其安全性基於格問題，而最常見的格問題是—最短格向量問題，和它的變形—最短理想格向量問題。在本文中，我們分別對這兩個問題進行計算量的估計；也就是對格密碼系統的安全參數給出更好的下界。更仔細地說，我們分別以GPU實作格列舉演算法(lattice enumeration algorithm)和格篩演算法(lattice sieve algorithm)，我們的實作中，都達到了該演算法的最高效率實作的記錄，因此，可以更合理的推估格問題的實際複雜度，以提供格密碼系統在參數選取時的依據。另一方面，在密碼系統效率的角度上，我們提出第一個硬體實作的格金鑰交換系統，瞭解在實務上格密碼系統的效率和成本。更詳細地說，我們實作於Usenix Security 2016由Alkim, Ducas, Pöpplemann和Schwabe提出的Newhope格金鑰交換系統，並達到目前時間面積乘積最佳之格金鑰交換系統硬體實作。因此，在可接受的加密時間內，可推知合理之實際可用的格密碼系統參數上界。

關鍵字

密碼學 ； 後量子密碼學 ； 格密碼學 ； 金鑰交換 ； 平行計算 ； 最短格向量問題 ； 最短理想格向量問題 ； 顯示晶片 ； 雲端運算 ； 格列舉演算法 ； 格極速列舉演算法 ； 格篩演算法 ； 格高斯篩演算法 ； 硬體實作 ； 現場可程式化邏輯閘陣列

並列摘要

The threat of the quantum computer is a huge problem for modern cryptography, and post-quantum cryptography aims to develop the cryptosystem, which may potentially resist attacks from quantum computers. Lattice-based cryptography is one of the most promising areas of post-quantum cryptography. In this thesis, we focus on the two aspects of lattice-based cryptography: security and efficiency, which are the most important properties for a practical cryptosystem.
The security of lattice-based cryptosystems is based on lattice problems. The shortest vector problem is the central problem of lattice problems, and its variant, the shortest vector problem over the ideal lattice, also is one of the most important problems for a lattice-based cryptosystem. We estimate the respective hardness for these two problems, that is, we give a concrete lower bound for the security parameters of the lattice-based cryptosystem. More precisely, we improve and implement the lattice enumeration algorithm for the shortest vector problem and the sieve algorithm for the shortest vector problem over the ideal lattice, respectively.
In our results, we achieve the best efficiency for the implementation of these two algorithms. Thus, we can estimate the computation cost for these two problems in order to provide a way to select the parameters of lattice-based cryptosystems. On the other hand, with regard to efficiency, we begin by executing the first hardware implementation of lattice-based key exchange protocol—Newhope, which is proposed by Alkim, Ducas, Pöpplemann, and Schwabe in Usenix Security 2016.
We achieve the best time-area product implementation of post-quantum key exchanges in a state-of-the-art environment. Therefore, our results provide a way to estimate the upper bound of the security parameters of lattice-based cryptosystems within an acceptable encryption time.

並列關鍵字

Cryptography ； Lattice ； lattice-based cryptography ； Shortest Vector Problem ； LWE ； RLWE ； GPU ； Cloud Computing ； Enumeration ； Extreme Pruning ； Sieve algorithm ； Gauss Sieve ； hardware implementation ； FPGA

參考文獻

[ABB10a] Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice(H)IBE in the standard model. InAdvances in Cryptology - EURO-CRYPT 2010, 29th Annual International Conference on the Theoryand Applications of Cryptographic Techniques, French Riviera, May 30- June 3, 2010. Proceedings, pages 553–572, 2010.[ABB10b] Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delega-tion in fixed dimension and shorter-ciphertext hierarchical IBE. In TalRabin, editor,Advances in Cryptology - CRYPTO 2010, 30th AnnualCryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010.Proceedings, volume 6223 ofLecture Notes in Computer Science, pages98–115. Springer, 2010.[AD97]Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem withworst-case/average-case equivalence. InProceedings of the twenty-ninthannual ACM symposium on Theory of computing, STOC ’97, pages284–293, New York, NY, USA, 1997. ACM.[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe.Post-quantum key exchange - A new hope. In Thorsten Holz and StefanSavage, editors,25th USENIX Security Symposium, USENIX Security16, Austin, TX, USA, August 10-12, 2016., pages 327–343. USENIXAssociation, 2016.72

[Ajt96]M. Ajtai. Generating hard instances of lattice problems (extended ab-stract). InProceedings of the twenty-eighth annual ACM symposium onTheory of computing, STOC ’96, pages 99–108, New York, NY, USA,1996. ACM.[Ajt97]Miklós Ajtai. The shortest vector problem in l2is np-hard for random-ized reductions.Electronic Colloquium on Computational Complexity(ECCC), 4(47), 1997.[AKS01] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm forthe shortest lattice vector problem. InAnnual ACM Symposium onTheory of Computing — STOC, pages 601–610, New York, NY, USA,2001. ACM.[AR05]Dorit Aharonov and Oded Regev. Lattice problems in np cap conp.J.ACM, 52(5):749–765, 2005.[BCD+16] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, MichaelNaehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Ste-bila. Frodo: Take off the ring! practical, quantum-secure key exchangefrom LWE. In Edgar R. Weippl, Stefan Katzenbeisser, ChristopherKruegel, Andrew C. Myers, and Shai Halevi, editors,Proceedings of the2016 ACM SIGSAC Conference on Computer and Communications Se-curity, Vienna, Austria, October 24-28, 2016, pages 1006–1018. ACM,2016.[BCLvV16] Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, andChristine van Vredendaal. NTRU prime.IACR Cryptology ePrintArchive, 2016:461, 2016.[BCNS15] Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila.Post-quantum key exchange for the TLS protocol from the ring learning73

with errors problem. In2015 IEEE Symposium on Security and Pri-vacy, SP 2015, San Jose, CA, USA, May 17-21, 2015, pages 553–570.IEEE Computer Society, 2015.[BDGL16] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New di-rections in nearest neighbor searching with applications to lattice siev-ing. In Robert Krauthgamer, editor,Proceedings of the Twenty-SeventhAnnual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016,Arlington, VA, USA, January 10-12, 2016, pages 10–24. SIAM, 2016.[BDK+17] Joppe W. Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyuba-shevsky, John M. Schanck, Peter Schwabe, and Damien Stehlé. CRYS-TALS - kyber: a cca-secure module-lattice-based KEM.IACR Cryp-tology ePrint Archive, 2017:634, 2017.[BGJ13] Anja Becker, Nicolas Gama, and Antoine Joux. Solving shortest andclosest vector problems: The decomposition approach.IACR Cryptol-ogy ePrint Archive, 2013:685, 2013.[BK16]Mehran Mozaffari Kermani Brian Koziel, Reza Azarderakhsh. Fasthardware architectures for supersingular isogeny diffie-hellman key ex-change on fpga. Cryptology ePrint Archive, Report 2016/1044, 2016.http://eprint.iacr.org/2016/1044.[BL16]Anja Becker and Thijs Laarhoven. Efficient (ideal) lattice sieving usingcross-polytope LSH. In David Pointcheval, Abderrahmane Nitaj, andTajjeeddine Rachidi, editors,Progress in Cryptology - AFRICACRYPT2016 - 8th International Conference on Cryptology in Africa, Fes, Mo-rocco, April 13-15, 2016, Proceedings, volume 9646 ofLecture Notes inComputer Science, pages 3–23. Springer, 2016.74

[BLP+13] Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, andDamien Stehlé. Classical hardness of learning with errors. In DanBoneh, Tim Roughgarden, and Joan Feigenbaum, editors,Symposiumon Theory of Computing Conference, STOC’13, Palo Alto, CA, USA,June 1-4, 2013, pages 575–584. ACM, 2013.[BLR08] Johannes Buchmann, Richard Lindner, and Markus Rückert. Explicithard instances of the shortest vector problem. InPQCrypto, pages79–94, 2008.[BNvdP14] Joppe W. Bos, Michael Naehrig, and Joop van de Pol. Sieving for short-est vectors in ideal lattices: a practical perspective.IACR CryptologyePrint Archive, 2014:880, 2014.[BSNK19] Kanad Basu, Deepraj Soni, Mohammed Nabeel, and Ramesh Karri.Nist post-quantum cryptography-a hardware evaluation study.IACRCryptology ePrint Archive, 2019:47, 2019.[BV11a]Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomor-phic encryption from (standard) lwe.Electronic Colloquium on Com-putational Complexity (ECCC), 18:109, 2011.[BV11b] Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic en-cryption from ring-lwe and security for key dependent messages. InPhillip Rogaway, editor,Advances in Cryptology - CRYPTO 2011 -31st Annual Cryptology Conference, Santa Barbara, CA, USA, August14-18, 2011. Proceedings, volume 6841 ofLecture Notes in ComputerScience, pages 505–524. Springer, 2011.[CIV16]Wouter Castryck, Ilia Iliashenko, and Frederik Vercauteren. Prov-ably weak instances of ring-lwe revisited. In Marc Fischlin and Jean-Sébastien Coron, editors,Advances in Cryptology - EUROCRYPT 201675

- 35th Annual International Conference on the Theory and Applicationsof Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Pro-ceedings, Part I, volume 9665 ofLecture Notes in Computer Science,pages 147–167. Springer, 2016.[CLLT16] Jean-Sébastien Coron, Moon Sung Lee, Tancrede Lepoint, and MehdiTibouchi. Cryptanalysis of ggh15 multilinear maps. InAnnual Inter-national Cryptology Conference, pages 607–628. Springer, 2016.[CLN16] Craig Costello, Patrick Longa, and Michael Naehrig. Efficient algo-rithms for supersingular isogeny diffie-hellman. In Matthew Robshawand Jonathan Katz, editors,Advances in Cryptology - CRYPTO 2016 -36th Annual International Cryptology Conference, Santa Barbara, CA,USA, August 14-18, 2016, Proceedings, Part I, volume 9814 ofLectureNotes in Computer Science, pages 572–601. Springer, 2016.[CMV+15] Donald Donglong Chen, Nele Mentens, Frederik Vercauteren, Su-joy Sinha Roy, Ray C. C. Cheung, Derek Pao, and Ingrid Verbauwhede.High-speed polynomial multiplication architecture for ring-lwe and SHEcryptosystems.IEEE Trans. on Circuits and Systems, 62-I(1):157–166,2015.[CN11]Yuanmi Chen and Phong Q. Nguyen. Bkz 2.0: Better lattice securityestimates. InProceedings of the 17th International Conference on TheTheory and Application of Cryptology and Information Security, ASI-ACRYPT’11, pages 1–20, Berlin, Heidelberg, 2011. Springer-Verlag.[Cra96]Richard E. Crandall.Topics in advanced scientific computation.Springer-Telos, 1996.[CS97]Don Coppersmith and Adi Shamir. Lattice attacks on ntru. InEURO-CRYPT, pages 52–61, 1997.76