臺灣博碩士論文加值系統

在近年，量子電腦的技術蓬勃發展，其潛在計算能力威脅了古典密碼學的系統安全性；因此，後量子密碼學應運而生，旨在發展可抵抗量子電腦攻擊的密碼系統。格密碼學是後量子密碼學中最有潛力的一個子領域，而本論文探討格密碼系統的中兩個最重要的面向：安全與效率。對於一個格密碼系統，其安全性基於格問題，而最常見的格問題是—最短格向量問題，和它的變形—最短理想格向量問題。在本文中，我們分別對這兩個問題進行計算量的估計；也就是對格密碼系統的安全參數給出更好的下界。更仔細地說，我們分別以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.

Contents
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Security Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Hardware Implementation . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Contributions and Roadmap . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Definition and Notation . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Lattice Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Lattice Basis Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Lattice Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.1 Enumeration using Extreme Pruning . . . . . . . . . . . . . .14
2.5 Sieving Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 Gauss Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 Gauss Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 CUDA Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Hardness of Lattice Problem from Enumeration . . . . . . . . 24
3.1 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4 Hardness of Lattice Problem from Sieve Algorithm . . . . . . 31
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Lifting technique for Ideal Lattices . . . . . . . . . . . . . . . .. 33
4.2.1 Lifting Prime Cyclotomic Polynomials . . . . . . . . . . . . . 33
4.2.2 Norms and Inner Products . . . . . . . . . . . . . . . . . . . . . . 34
4.2.3 Lazy Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.4 Generalizing Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3.1 Outer Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 39
4.3.2 Inner Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.4.1 Vector Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 41
4.4.2 Instruction-Level Parallelism . . . . . . . . . . . . . . . . . . . . . 42
4.4.3 More Kernel Optimizations . . . . . . . . . . . . . . . . . . . . . . 42
4.4.4 On Faster Convolution . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.4.5 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 43
4.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.5.1 Parallel Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5.2 Ideal Lattices versus General Lattices . . . . . . . . . . . . . 45
4.5.3 Chronological Behavior . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5.4 Hardness Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.6 Application towards Cryptosystem Construction . . . . . . . 49
5 Hardware Implementation of Lattice-based Key Exchange . 51
5.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.1.1 NewHope Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.1.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 53
5.2 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2.1 Random Number Generator . . . . . . . . . . . . . . . . . . 58
5.2.2 Number-Theoretical Transform . . . . . . . . . . . . . . . 59
5.2.3 Reconciliation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
A Proof for key exchange protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
A.1 Proof of the input size and output size ofK-REDbutterfly . . . . . . . 93

[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
signature and encryption schemes.Tatra Mountains Mathematical Pub-lications, 53(1):81–102, 2012.[ELOS15] Yara Elias, Kristin E. Lauter, Ekin Ozman, and Katherine E. Stange.Provably weak instances of ring-lwe. In Gennaro and Robshaw [GR15],pages 63–92.[FCMS19] Gabriel Falcao, Filipe Cabeleira, Artur Mariano, and Luis Paulo Santos.Heterogeneous implementation of a voronoi cell-based svp solver.IEEEAccess, 7:127012–127023, 2019.[FK15]Masaharu Fukase and Kenji Kashiwabara. An accelerated algorithmfor solving SVP based on statistical analysis.JIP, 23(1):67–80, 2015.[FP83]U. Fincke and Michael Pohst. A procedure for determining algebraicintegers of given norm. InEUROCAL, pages 194–202, 1983.[FY14]Heba Mohammed Fadhil and Mohammed Issam Younis. Article: Paral-lelizing rsa algorithm on multicore cpu and gpu.International Journalof Computer Applications, 87(6):15–22, February 2014. Full text avail-able.[Gen09]Craig Gentry. Fully homomorphic encryption using ideal lattices. InAnnual ACM Symposium on Theory of Computing — STOC, pages169–178, 2009.[GFS+12] Norman Göttert, Thomas Feller, Michael Schneider, Johannes A. Buch-mann, and Sorin A. Huss. On the design of hardware building blocksfor modern lattice-based encryption schemes. In Emmanuel Prouffand Patrick Schaumont, editors,Cryptographic Hardware and Embed-ded Systems - CHES 2012 - 14th International Workshop, Leuven, Bel-gium, September 9-12, 2012. Proceedings, volume 7428 ofLecture Notesin Computer Science, pages 512–529. Springer, 2012.78
[GGH96] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryp-tosystems from lattice reduction problems.Electronic Colloquium onComputational Complexity (ECCC), 3(56), 1996.[GGH11] Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Collision-free hash-ing from lattice problems. In Oded Goldreich, editor,Studies in Com-plexity and Cryptography. Miscellanea on the Interplay between Ran-domness and Computation - In Collaboration with Lidor Avigad, MihirBellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman,Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan,Salil Vadhan, Avi Wigderson, David Zuckerman, volume 6650 ofLec-ture Notes in Computer Science, pages 30–39. Springer, 2011.[GGH13] Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinearmaps from ideal lattices. In Thomas Johansson and Phong Q. Nguyen,editors,Advances in Cryptology - EUROCRYPT 2013, 32nd AnnualInternational Conference on the Theory and Applications of Crypto-graphic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, vol-ume 7881 ofLecture Notes in Computer Science, pages 1–17. Springer,2013.[GM06]D. Goldstein and A. Mayer. On the equidistribution of hecke points.Forum Mathematicum, 15(2):165–189, 2006.[GN08]Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. InEurocrypt, pages 31–51, 2008.[GNR10] Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumera-tion using extreme pruning. InEUROCRYPT, pages 257–278, 2010.[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors forhard lattices and new cryptographic constructions. In Cynthia Dwork,79
editor,Proceedings of the 40th Annual ACM Symposium on Theoryof Computing, Victoria, British Columbia, Canada, May 17-20, 2008,pages 197–206. ACM, 2008.[GR15]Rosario Gennaro and Matthew Robshaw, editors.Advances in Cryp-tology - CRYPTO 2015 - 35th Annual Cryptology Conference, SantaBarbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume9215 ofLecture Notes in Computer Science. Springer, 2015.[GS16]Shay Gueron and Fabian Schlieker. Speeding up r-lwe post-quantumkey exchange. InNordic Conference on Secure IT Systems, pages 187–198. Springer, 2016.[Her50]C. Hermite. Extraits de lettres de m. ch. hermite a m. jacobi sur dif-ferents objects de lá théorie des nombres.Journal fur die reine undangewandte Mathematik, 1850:261–278, 1850.[HMO+16] James Howe, Ciara Moore, Máire O’Neill, Francesco Regazzoni, TimGüneysu, and K. Beeden. Standard lattices in hardware. InProceedingsof the 53rd Annual Design Automation Conference, DAC 2016, Austin,TX, USA, June 5-9, 2016, pages 162:1–162:6. ACM, 2016.[HPS98]Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ring-based public key cryptosystem. InANTS, pages 267–288, 1998.[HPS11]Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Algorithms forthe shortest and closest lattice vector problems. InCoding and Cryp-tology - Third International Workshop, IWCC 2011, Qingdao, China,May 30-June 3, 2011. Proceedings, pages 159–190, 2011.[HVP10] Jens Hermans, Frederik Vercauteren, and Bart Preneel. Speed recordsfor ntru. InCT-RSA, pages 73–88, 2010.80
[IKMT14] Tsukasa Ishiguro, Shinsaku Kiyomoto, Yutaka Miyake, and TsuyoshiTakagi. Parallel gauss sieve algorithm: Solving the SVP challenge overa 128-dimensional ideal lattice. In Hugo Krawczyk, editor,Public-KeyCryptography - PKC 2014 - 17th International Conference on Prac-tice and Theory in Public-Key Cryptography, Buenos Aires, Argentina,March 26-28, 2014. Proceedings, volume 8383 ofLecture Notes in Com-puter Science, pages 411–428. Springer, 2014.[JGCS19] Arpan Jati, Naina Gupta, Anupam Chattopadhyay, and Somitra Ku-mar Sanadhya. Spqcop: Side-channel protected post-quantum crypto-processor. Cryptology ePrint Archive, Report 2019/765, 2019.https://eprint.iacr.org/2019/765.[KAKJ17] Brian Koziel, Reza Azarderakhsh, Mehran Mozaffari Kermani, andDavid Jao. Post-quantum cryptography on FPGA based on isogenieson elliptic curves.IEEE Trans. on Circuits and Systems, 64-I(1):86–99,2017.[Kan83]Ravi Kannan. Improved algorithms for integer programming and re-lated lattice problems. InSTOC, pages 193–206, 1983.[KC14]Po-Chun Kuo and Chen-Mou Cheng. Lattice-based cryptanalysis - howto estimate the security parameter of lattice-based cryptosystem. In2014 IEEE International Conference on Consumer Electronics - Tai-wan, pages 53–54, May 2014.[KCH+19] Po-Chun Kuo, Yu-Wei Chen, Yuan-Che Hsu, Chen-Mou Cheng, Wen-Ding Li, and Bo-Yin Yang. High-performance post-quantum key ex-change on FPGAs. accepted by Journal of Information Science andEngineering, 2019.81
[KCLY20] Po-Chun Kuo, Chen-Mou Cheng, Wen-Ding Li, and Bo-Yin Yang. Par-allelization on Gauss sieve algorithm over ideal lattice. accepted byJournal of Information Science and Engineering, 2020.[KDV+11] Stéphanie Kerckhof, François Durvaux, Nicolas Veyrat-Charvillon,Francesco Regazzoni, Guerric Meurice de Dormale, and François-XavierStandaert. Compact FPGA implementations of the five SHA-3 finalists.In Emmanuel Prouff, editor,Smart Card Research and Advanced Appli-cations - 10th IFIP WG 8.8/11.2 International Conference, CARDIS2011, Leuven, Belgium, September 14-16, 2011, Revised Selected Pa-pers, volume 7079 ofLecture Notes in Computer Science, pages 217–233. Springer, 2011.[KLC+17] Po-Chun Kuo, Wen-Ding Li, Yu-Wei Chen, Yuan-Che Hsu, Chen-MouCheng, and Bo-Yin Yang. High-performance post-quantum key ex-change on fpgas.IACR Cryptology ePrint Archive, 2017:690, 2017.[KS01]Henrik Koy and Claus-Peter Schnorr. Segment lll-reduction of latticebases. In Joseph H. Silverman, editor,Cryptography and Lattices, Inter-national Conference, CaLC 2001, Providence, RI, USA, March 29-30,2001, Revised Papers, volume 2146 ofLecture Notes in Computer Sci-ence, pages 67–80. Springer, 2001.[KSD+11] Po-Chun Kuo, Michael Schneider, Özgür Dagdelen, Jan Reichelt, Jo-hannes A. Buchmann, Chen-Mou Cheng, and Bo-Yin Yang. Extremeenumeration on GPU and in clouds - - how many dollars you need tobreak SVP challenges -. In Bart Preneel and Tsuyoshi Takagi, editors,Cryptographic Hardware and Embedded Systems - CHES 2011 - 13thInternational Workshop, Nara, Japan, September 28 - October 1, 2011.Proceedings, volume 6917 ofLecture Notes in Computer Science, pages176–191. Springer, 2011.82
[KTX08] Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Concurrentlysecure identification schemes based on the worst-case hardness of latticeproblems. InASIACRYPT, pages 372–389, 2008.[Kuo11]Po-Chun Kuo. Extreme Enumeration on GPU and in Clouds. Master’sthesis, National Taiwan University, Taiwan, 2011.[KY76]D. Knuth and A. Yao.Algorithms and Complexity: New Directions andRecent Results, chapter The complexity of nonuniform random numbergeneration. Academic Press, 1976.[Laa15]Thijs Laarhoven. Sieving for shortest vectors in lattices using angularlocality-sensitive hashing. In Gennaro and Robshaw [GR15], pages 3–22.[LLL14]Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors.SelectedAreas in Cryptography - SAC 2013 - 20th International Conference,Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers,volume 8282 ofLecture Notes in Computer Science. Springer, 2014.[LM09]Vadim Lyubashevsky and Daniele Micciancio. On bounded distancedecoding, unique shortest vectors, and the minimum distance problem.InCrypto, pages 577–594, 2009.[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and AlonRosen. SWIFFT: A modest proposal for FFT hashing. In Kaisa Ny-berg, editor,Fast Software Encryption, 15th International Workshop,FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Se-lected Papers, volume 5086 ofLecture Notes in Computer Science, pages54–72. Springer, 2008.83
[LMvdP15] Thijs Laarhoven, Michele Mosca, and Joop van de Pol. Finding shortestlattice vectors faster using quantum search.Des. Codes Cryptography,77(2-3):375–400, 2015.[LN16]Patrick Longa and Michael Naehrig. Speeding up the number theoretictransform for faster ideal lattice-based cryptography. In Sara Forestiand Giuseppe Persiano, editors,Cryptology and Network Security - 15thInternational Conference, CANS 2016, Milan, Italy, November 14-16,2016, Proceedings, volume 10052 ofLecture Notes in Computer Science,pages 124–139, 2016.[LP11]Richard Lindner and Chris Peikert. Better key sizes (and attacks) forlwe-based encryption. InCT-RSA, pages 319–339, 2011.[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal latticesand learning with errors over rings. InEUROCRYPT, pages 1–23, 2010.[LW16]Bingxin Liu and Huapeng Wu. Efficient multiplication architectureover truncated polynomial ring for ntruencrypt system. InIEEE Inter-national Symposium on Circuits and Systems, ISCAS 2016, Montréal,QC, Canada, May 22-25, 2016, pages 1174–1177. IEEE, 2016.[MB16]Artur Mariano and Christian H. Bischof. Enhancing the scalabilityand memory usage of hashsieve on multi-core cpus. In24th EuromicroInternational Conference on Parallel, Distributed, and Network-BasedProcessing, PDP 2016, Heraklion, Crete, Greece, February 17-19, 2016,pages 545–552. IEEE Computer Society, 2016.[MBL15] Artur Mariano, Christian H. Bischof, and Thijs Laarhoven. Parallel(probable) lock-free hash sieve: A practical sieving algorithm for theSVP. In44th International Conference on Parallel Processing, ICPP84
2015, Beijing, China, September 1-4, 2015, pages 590–599. IEEE Com-puter Society, 2015.[MDB14] Artur Mariano, Özgür Dagdelen, and Christian H. Bischof. A compre-hensive empirical comparison of parallel listsieve and gausssieve. InLuís M. B. Lopes, Julius Zilinskas, Alexandru Costan, Roberto G.Cascella, Gabor Kecskemeti, Emmanuel Jeannot, Mario Cannataro,Laura Ricci, Siegfried Benkner, Salvador Petit, Vittorio Scarano, JoséGracia, Sascha Hunold, Stephen L. Scott, Stefan Lankes, ChristianLengauer, Jesús Carretero, Jens Breitbart, and Michael Alexander, ed-itors,Euro-Par 2014: Parallel Processing Workshops - Euro-Par 2014International Workshops, Porto, Portugal, August 25-26, 2014, RevisedSelected Papers, Part I, volume 8805 ofLecture Notes in Computer Sci-ence, pages 48–59. Springer, 2014.[Mer]Duane (Nvidia Coorporation) Merrill. The CUB Library.[MR07]Daniele Micciancio and Oded Regev. Worst-case to average-case re-ductions based on Gaussian measure.SIAM Journal on Computing,37(1):267–302, 2007. Preliminary version in FOCS 2004.[MS11]Benjamin Milde and Michael Schneider. A parallel implementationof gausssieve for the shortest vector problem in lattices. In VictorMalyshkin, editor,Parallel Computing Technologies - 11th Interna-tional Conference, PaCT 2011, Kazan, Russia, September 19-23, 2011.Proceedings, volume 6873 ofLecture Notes in Computer Science, pages452–458. Springer, 2011.[MV10a] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single ex-ponential time algorithm for most lattice problems based on voronoi cellcomputations. In Leonard J. Schulman, editor,Proceedings of the 42nd85
ACM Symposium on Theory of Computing, STOC 2010, Cambridge,Massachusetts, USA, 5-8 June 2010, pages 351–358. ACM, 2010.[MV10b] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential timealgorithms for the shortest vector problem. InSODA’10, pages 1468–1480, 2010.[Ngu99]Phong Q. Nguyen. Cryptanalysis of the goldreich-goldwasser-halevicryptosystem from crypto ’97. InCRYPTO, pages 288–304, 1999.[NS04]Phong Q. Nguyen and Damien Stehlé. Floating-Point LLL Revisited.Research Report RR-5387, INRIA, 2004.[NV08]P. Q. Nguyen and T. Vidick. Sieve algorithms for the shortest vectorproblem are practical.J. of Mathematical Cryptology, 2(2), 2008.[NV09]Phong Q. Nguyen and Brigitte Valle.The LLL Algorithm: Survey andApplications. Springer Publishing Company, Incorporated, 1st edition,2009.[NVI15]NVIDIA. CUDA C programming guide 7.5.http://docs.nvidia.com/cuda/cuda-c-programming-guide/, 2015.[OG17]Tobias Oder and Tim Güneysu. Implementing the newhope-simple keyexchange on low-cost fpgas. InProgress in Cryptology - LATINCRYPT2017 - 6th International Conference on Cryptology and InformationSecurity in Latin America, Cuba, September 20-22, 2017, Proceedings,2017.[Ope12]OpenCores. SHA3(KECCAK).https://opencores.org/project,sha3, 2012. [Online; accessed 09-November-2012, updated 02-December-2016].86
[oSN16]National Institute of Standards and Technology (NIST). POST-QUANTUM CRYPTO PROJECT.http://csrc.nist.gov/groups/ST/post-quantum-crypto/, 2016. [Online; accessed 29-February-2016].[Pei09a]Chris Peikert. Public-key cryptosystems from the worst-case shortestvector problem: extended abstract. In Michael Mitzenmacher, editor,Proceedings of the 41st Annual ACM Symposium on Theory of Comput-ing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages333–342. ACM, 2009.[Pei09b]Chris Peikert. Some recent progress in lattice-based cryptography. InOmer Reingold, editor,Theory of Cryptography, 6th Theory of Cryptog-raphy Conference, TCC 2009, San Francisco, CA, USA, March 15-17,2009. Proceedings, volume 5444 ofLecture Notes in Computer Science,page 72. Springer, 2009.[Pei14]Chris Peikert. Lattice cryptography for the internet. In MicheleMosca, editor,Post-Quantum Cryptography - 6th International Work-shop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Pro-ceedings, volume 8772 ofLecture Notes in Computer Science, pages197–219. Springer, 2014.[PG13]Thomas Pöppelmann and Tim Güneysu. Towards practical lattice-based public-key encryption on reconfigurable hardware. In Lange et al.[LLL14], pages 68–85.[PS08]Xavier Pujol and Damien Stehlé. Rigorous and efficient short latticevectors enumeration. InAsiacrypt, pages 390–405, 2008.87
[PS09]Xavier Pujol and Damien Stehle. Solving the shortest lattice vectorproblem in time22.465n. Cryptology ePrint Archive, Report 2009/605,2009. http://eprint.iacr.org/.[PVW08] Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A frameworkfor efficient and composable oblivious transfer. In David A. Wagner,editor,Advances in Cryptology - CRYPTO 2008, 28th Annual Interna-tional Cryptology Conference, Santa Barbara, CA, USA, August 17-21,2008. Proceedings, volume 5157 ofLecture Notes in Computer Science,pages 554–571. Springer, 2008.[Reg05]Oded Regev. On lattices, learning with errors, random linear codes,and cryptography. InSTOC, pages 84–93, 2005.[Reg09]Oded Regev. On lattices, learning with errors, random linear codes,and cryptography.J. ACM, 56(6):1–40, 2009.[RRVV15] Oscar Reparaz, Sujoy Sinha Roy, Frederik Vercauteren, and IngridVerbauwhede. A masked ring-lwe implementation. In Tim Güneysuand Helena Handschuh, editors,Cryptographic Hardware and Embed-ded Systems - CHES 2015 - 17th International Workshop, Saint-Malo,France, September 13-16, 2015, Proceedings, volume 9293 ofLectureNotes in Computer Science, pages 683–702. Springer, 2015.[RVM+14] Sujoy Sinha Roy, Frederik Vercauteren, Nele Mentens, Donald Dong-long Chen, and Ingrid Verbauwhede. Compact ring-lwe cryptoproces-sor. In Lejla Batina and Matthew Robshaw, editors,CryptographicHardware and Embedded Systems - CHES 2014 - 16th InternationalWorkshop, Busan, South Korea, September 23-26, 2014. Proceedings,volume 8731 ofLecture Notes in Computer Science, pages 371–391.Springer, 2014.88
[RVV13] Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede. Highprecision discrete gaussian sampling on fpgas. In Lange et al. [LLL14],pages 383–401.[Sch03]Claus-Peter Schnorr. Lattice reduction by random sampling and birth-day methods. In Helmut Alt and Michel Habib, editors,STACS 2003,20th Annual Symposium on Theoretical Aspects of Computer Science,Berlin, Germany, February 27 - March 1, 2003, Proceedings, volume2607 ofLecture Notes in Computer Science, pages 145–156. Springer,2003.[Sch11]Michael Schneider. Analysis of gauss-sieve for solving the shortest vec-tor problem in lattices. In Naoki Katoh and Amit Kumar, editors,WALCOM: Algorithms and Computation - 5th International Workshop,WALCOM 2011, New Delhi, India, February 18-20, 2011. Proceed-ings, volume 6552 ofLecture Notes in Computer Science, pages 89–97.Springer, 2011.[Sch13]Michael Schneider. Sieving for shortest vectors in ideal lattices. InAmr Youssef, Abderrahmane Nitaj, and Aboul Ella Hassanien, edi-tors,Progress in Cryptology - AFRICACRYPT 2013, 6th InternationalConference on Cryptology in Africa, Cairo, Egypt, June 22-24, 2013.Proceedings, volume 7918 ofLecture Notes in Computer Science, pages375–391. Springer, 2013.[SD16]Noah Stephens-Davidowitz. Dimension-preserving reductions betweenlattice problems.h ttp://www. noahsd. com/latticeproblems. pdf, 2016.[SE91]Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Im-proved practical algorithms and solving subset sum problems. InPro-ceedings of the 8th International Symposium on Fundamentals of Com-89
putation Theory, FCT ’91, pages 68–85, London, UK, 1991. Springer-Verlag.[SM16]Douglas Stebila and Michele Mosca. Post-quantum key exchange forthe internet and the open quantum safe project. InInternational Con-ference on Selected Areas in Cryptography, pages 14–37. Springer, 2016.[Vou]Panagiotis Voulgaris. Gauss sieve implementation by panagiotis voul-garis.https://cseweb.ucsd.edu/~pvoulgar/impl.html.[WLTB11] Xiaoyun Wang, Mingjie Liu, Chengliang Tian, and Jingguo Bi. Im-proved nguyen-vidick heuristic sieve algorithm for shortest vector prob-lem. InProceedings of the 6th ACM Symposium on Information,Computer and Communications Security, ASIACCS 2011, Hong Kong,China, March 22-24, 2011, pages 1–9, 2011.[WT09]Knut Wold and Chik How Tan. Analysis and enhancement of randomnumber generator in FPGA based on oscillator rings.Int. J. Reconfig.Comp., 2009:501672:1–501672:8, 2009.[YKYC17] Shang-Yi Yang, Po-Chun Kuo, Bo-Yin Yang, and Chen-Mou Cheng.Gauss sieve algorithm on gpus. In Helena Handschuh, editor,Top-ics in Cryptology - CT-RSA 2017 - The Cryptographers’ Track at theRSA Conference 2017, San Francisco, CA, USA, February 14-17, 2017,Proceedings, volume 10159 ofLecture Notes in Computer Science, pages39–57. Springer, 2017.[YXW17] Yang Yu, Guangwu Xu, and Xiaoyun Wang. Provably secure NTRUinstances over prime cyclotomic rings. InPublic-Key Cryptography -PKC 2017 - 20th IACR International Conference on Practice and The-ory in Public-Key Cryptography, Amsterdam, The Netherlands, March28-31, 2017, Proceedings, Part I, pages 409–434, 2017.90
[ZPH13] Feng Zhang, Yanbin Pan, and Gengran Hu. A three-level sieve algo-rithm for the shortest vector problem. InSelected Areas in Cryptography- SAC 2013 - 20th International Conference, Burnaby, BC, Canada,August 14-16, 2013, Revised Selected Papers, pages 29–47, 2013.[ZYC+20] Neng Zhang, Bohan Yang, Chen Chen, Shouyi Yin, Shaojun Wei, andLeibo Liu. Highly efficient architecture of newhope-nist on fpga usinglow-complexity ntt/intt.IACR Transactions on Cryptographic Hard-ware and Embedded Systems, pages 49–72, 2020.