臺灣博碩士論文加值系統

廣受使用的NTRU密碼系統和許多可証明安全性的格基密碼系統的安全性都直接和最短格向量問題有直接相關。於此研究中，我們改進數點解最短格向量問題之演算法，至今，經由這些改進，在解SVP的公開挑戰賽中我們分別拿下第一、二、三名的成績。
我們改進目前效率最高的極速列舉演算法，並分別經由MapReduce實作在雲端上和經由CUDA實作在顯示晶片上。藉由這兩個實作，可以價錢來評估一格基密碼系統的難度，意即，要花多少錢向雲端計算提供商租運算量去破解一格基密碼系統。
我們的實作使用8張nVidia顯卡即可在兩天內破解維度114,116的最短格向量問題；另外，我們也花費2300美金解出維度120的問題。

The complexity of SVP (Shortest Vector Problem) is directly related to the security of NTRU and the provable level of security of many recently proposed lattice-based cryptosystems.
We integrate several recent algorithmic improvements for solving SVP and take rst, second, and third place repectively at dimension 120, 116, and 114 on the SVP Challenge Hall of Fame.
Speci cally, our improvements to the recent Extreme Pruning in enumeration approach include a better set of pruning rules, code to take advantage of Clouds of commodity PCs (via the MapReduce framework), and the use of NVIDIA''s Graphics Processing Units (GPUs). We may now reasonably estimate the cost of a wide range of SVPs in U.S. dollars, as rent paid to cloud-computing service providers, which is arguably a simpler and more practical measure of complexity.
Our implementation allows us to fi nd a short vector at dimension 116 and 114 using 8 nVidia video cards in less than two days. As shown the price of security level, we spend 2300 U.S. dollar for renting machines from Amazon and solve SVP with dimension 120.

Abstract i
1 Introduction 2
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Cloud Computing, Amazon EC2, and GPU . . . . . . . . . . . . . . . 5
1.4 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Lattice Problem 10
2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Problem Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Related Cryptosystems and Related Problems . . . . . . . . . . . . . 12
3 Lattice Enumeration 14
3.1 Lattice Reduction Algorithm . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Enumeration using Extreme Pruning . . . . . . . . . . . . . . . . . . 16
4 Parallel, Variants and Analysis 20
4.1 Parallel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 BKZ with Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Bounding Function Selection . . . . . . . . . . . . . . . . . . . . . . . 22
5 Implementation 24
5.1 Architecture Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6 Results 28
6.1 GPU Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 MapReduce Implementation . . . . . . . . . . . . . . . . . . . . . . . 32
6.3 Final Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
7 Conclusion 35

[AD97] Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worstcase/
average-case equivalence. In Proceedings of the twenty-ninth annual
ACM symposium on Theory of computing, STOC ''97, pages 284-293,
New York, NY, USA, 1997. ACM.
[Ajt96] M. Ajtai. Generating hard instances of lattice problems (extended abstract).
In Proceedings of the twenty-eighth annual ACM symposium on
Theory of computing, STOC ''96, pages 99-108, New York, NY, USA,
1996. ACM.
[Ajt98] Miklós Ajtai. The shortest vector problem in l2 is NP-hard for randomized
reductions (extended abstract). In Proceedings of the thirtieth
annual ACM symposium on Theory of computing, STOC ''98, pages 10-19, New York, NY, USA, 1998. ACM.
[AKS01] Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the
shortest lattice vector problem. In Annual ACM Symposium on Theory
of Computing -STOC , pages 601-610, New York, NY, USA, 2001.
ACM.
[AR05] Dorit Aharonov and Oded Regev. Lattice problems in NP intersect
coNP. J. ACM, 52(5):749-765, 2005.
[BLR08] Johannes Buchmann, Richard Lindner, and Markus Rückert. Explicit
hard instances of the shortest vector problem. In Johannes Buchmann
and Jintai Ding, editors, PQCrypto, volume 5299 of Lecture Notes in
Computer Science, pages 79-94. Springer, 2008.
[CS97] Don Coppersmith and Adi Shamir. Lattice attacks on ntru. In EURO-
CRYPT, pages 52-61, 1997.
[DG04] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing
on large clusters. In OSDI''04: Sixth Symposium on Operating
System Design and Implementation, San Francisco, CA, USA, December
2004.
[DHPS10] Jérémie Detrey, Guillaume Hanrot, Xavier Pujol, and Damien Stehlé.
Accelerating lattice reduction with FPGAs. In LATINCRYPT, volume
6212 of LNCS, pages 124-143. Springer, 2010.
[DS10] Özgür Dagdelen and Michael Schneider. Parallel enumeration of shortest
lattice vectors. In Euro-Par, volume 6272 of LNCS, pages 211-222.
Springer, 2010.
[FP83] U. Fincke and Michael Pohst. A procedure for determining algebraic
integers of given norm. In European Computer Algebra Conference, volume
162 of Lecture Notes in Computer Science, pages 194-202. Springer,
1983.
[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In
Michael Mitzenmacher, editor, Annual ACM Symposium on Theory of
Computing - STOC , pages 169-178. ACM, 2009.
[GGH96] Collision-free hashing from lattice problems, 1996. Appeared in the THEORY
OF CRYPTOGRAPHY LIBRARY and has been included in the
ePrint Archive. oded@theory.lcs.mit.edu 10500 received July 26th, 1996.
[GM03] Daniel Goldstein and Andrew Mayer. On the equidistribution of Hecke
points. Forum Mathematicum 2003, 15:2, pages 165-189, 2003.
[GN08] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In
Nigel P. Smart, editor, Eurocrypt, volume 4965 of Lecture Notes in Com-
puter Science, pages 31-51. Springer, 2008.
[GNR10] Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration
using extreme pruning. In Advances in Cryptology - EURO-
CRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages
257 278. Springer, 2010.
[Gol97] Public-key cryptosystems from lattice reduction problems. In CRYPTO,
pages 112-131, 1997.
[GPV08] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors
for hard lattices and new cryptographic constructions. In Annual ACM
Symposium on Theory of Computing -STOC 2008, pages 197-206.
ACM Press, 2008.
[GS10] Nicolas Gama and Michael Schneider. SVP Challenge, 2010. available
at http://www.latticechallenge.org/svp-challenge.
[Her50] C. Hermite. Extraits de lettres de m. ch. hermite a m. jacobi sur di erents
objects de lá théorie des nombres. Journal fur die reine und angewandte
Mathematik, 1850:261-278, 1850.
[HPS98] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. Ntru: A ringbased
public key cryptosystem. In ANTS, pages 267-288, 1998.
[HSB+10] Jens Hermans, Michael Schneider, Johannes Buchmann, Frederik Vercauteren,
and Bart Preneel. Parallel shortest lattice vector enumeration
on graphics cards. In Africacrypt 2010, volume 6055 of Lecture Notes in
Computer Science, pages 52-68. Springer, 2010.
[Kan83] Ravi Kannan. Improved algorithms for integer programming and related
lattice problems. In Annual ACM Symposium on Theory of Computing
-STOC 1983, pages 193-206. ACM Press, 1983.
[KH10] David B. Kirk and Wen-mei Hwu. Programming Massively Parallel Pro-
cessors: A Hands-on Approach. Morgan Kaufmann, 1 edition, February
2010.
[KLPS11] T. Kleinjung, A.K. Lenstra, D. Page, and N.P. Smart. Using the cloud to
determine key strengths. Cryptology ePrint Archive, Report 2011/254,
2011. http://eprint.iacr.org/.
[KS01] Henrik Koy and Claus-Peter Schnorr. Segment lll-reduction of lattice
bases. In Joseph H. Silverman, editor, CaLC, volume 2146 of Lecture
Notes in Computer Science, pages 67-80. Springer, 2001.
[KTX08] Akinori Kawachi, Keisuke Tanaka, and Keita Xagawa. Concurrently
secure identi cation schemes based on the worst-case hardness of lattice
problems. In ASIACRYPT, pages 372 389, 2008.
[Len83] H.W.jun. Lenstra. Integer programming with a xed number of variables.
Math. Oper. Res., 8:538-548, 1983.
[Len05] Arjen Lenstra. Key lengths. In Hossein Bidgoli, editor, Handbook of
Information Security. Wiley, December 2005.
[LLL82] Arjen Lenstra, Hendrik Lenstra, and László Lovász. Factoring polynomials
with rational coefficients. Mathematische Annalen, 4:515-534,
1982.
[LM09] Vadim Lyubashevsky and Daniele Micciancio. On bounded distance
decoding, unique shortest vectors, and the minimum distance problem.
In Shai Halevi, editor, Crypto, volume 5677 of Lecture Notes in Computer
Science, pages 577-594. Springer, 2009.
[LMPR08] Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon
Rosen. Swifft: A modest proposal for fft hashing. In FSE, pages 54-72,
2008.
[MR07] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions
based on Gaussian measure. SIAM Journal on Computing,
37(1):267-302, 2007. Preliminary version in FOCS 2004.
[MV10a] Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential
time algorithm for most lattice problems based on voronoi cell
computations. In STOC, pages 351-358. ACM, 2010.
[MV10b] Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time
algorithms for the shortest vector problem. In SODA 2010, pages 1468-
1480. ACM/SIAM, 2010.
[Ngu99] Cryptanalysis of the goldreich-goldwasser-halevi cryptosystem from
crypto ''97. In CRYPTO, 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 vector
problem are practical. J. of Mathematical Cryptology, 2(2), 2008.
[Pei08] A framework for efficient and composable oblivious transfer. In
CRYPTO, volume 5157, pages 554-571, 2008.
[PS08] Xavier Pujol and Damien Stehlé. Rigorous and e cient short lattice
vectors enumeration. In Advances in Cryptology ASIACRYPT 2008,
volume 5350 of Lecture Notes in Computer Science, pages 390 405.
Springer, 2008.
[PS09] Xavier Pujol and Damien Stehle. Solving the shortest lattice vector
problem in time 22:465n. Cryptology ePrint Archive, Report 2009/605,
2009. http://eprint.iacr.org/.
[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and
cryptography. In STOC, pages 84-93, 2005.
[Reg09] Oded Regev. On lattices, learning with errors, random linear codes, and
cryptography. J. ACM, 56(6):1-40, 2009.
[Reg10] Oded Regev. The learning with errors problem (invited survey). In IEEE
Conference on Computational Complexity, pages 191-204, 2010.
[Sch03] Claus-Peter Schnorr. Lattice reduction by random sampling and birthday
methods. In STACS, pages 145-156, 2003.
[SE94] Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved
practical algorithms and solving subset sum problems. Mathematical
Programming, 66:181-199, 1994.
[SH95] Claus-Peter Schnorr and Horst Helmut Hörner. Attacking the chor-rivest
cryptosystem by improved lattice reduction. In EUROCRYPT, volume
921 of LNCS, pages 1-12. Springer, 1995.
[SHK] Michael Schneider, Jens Hermans, and Po-Chun Kuo. Shortest lattice
vector enumeration on graphics cards, version 2.0. http://homes.esat.
kuleuven.be/~jhermans/gpuenum/index.html.
[Sho] Victor Shoup. Number theory library (NTL) for C++, version 5.5.2.
http://www.shoup.net/ntl/.