格子の最短ベクトル問題に対する離散的考察と並列計算アルゴリズム
DOI:
https://doi.org/10.51094/jxiv.60キーワード:
格子基底簡約、 並列計算、 Gram-Charlier展開、 効率的アルゴリズム抄録
格子の最短ベクトル問題は、短い格子ベクトルをいかに効率的に見つけるかという問題であ る。これまでは格子ベクトルの生成時に直交基底ベクトルに対する係数が一様に分布するとい うランダム仮定をもとに短い格子ベクトルが見つかる確率を推測してきた。ランダム仮定は連 続的なモデルであり、実際には短いベクトルは離散的に分布しているので同じ格子ベクトルが 複数回得られることがある。この論文では実験により格子ベクトルの重複について検証する。 また基底の評価関数を用いた並列環境における効率的な基底簡約の方法を提案する。
ダウンロード *前日までの集計結果を表示します
引用文献
Martin R. Albrecht, L ́eo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EURO- CRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II, volume 11477 of Lecture Notes in Computer Science, pages 717–746. Springer, 2019.
Michal Andrzejczak and Kris Gaj. A multiplatform parallel approach for lattice sieving algorithms. IACR Cryptol. ePrint Arch., 2021:973, 2020.
Yoshinori Aono and Phong Q. Nguyen. Random sampling revisited: Lattice enumeration with discrete pruning. In Jean-S ́ebastien Coron and Jesper Buus Nielsen, editors, Ad- vances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pages 65–102, 2017.
L ́aszl ́o Babai. On lov ́asz’ lattice reduction and the nearest lattice point problem. Combi- natorica, 6(1):1–13, 1986.
Joppe W. Bos, Michael Naehrig, and Joop van de Pol. Sieving for shortest vectors in ideal lattices: a practical perspective. Int. J. Appl. Cryptogr., 3(4):313–329, 2017.
O ̈zgu ̈r Dagdelen and Michael Schneider. Parallel enumeration of shortest lattice vectors. In Pasqua D’Ambra, Mario Rosario Guarracino, and Domenico Talia, editors, Euro-Par 2010 - Parallel Processing, 16th International Euro-Par Conference, Ischia, Italy, August31 - September 3, 2010, Proceedings, Part II, volume 6272 of Lecture Notes in Computer Science, pages 211–222. Springer, 2010.
TU Darmstadt. SVP Challenge. http://www.latticechallenge.org/svp-challenge/.
L ́eo Ducas, Marc Stevens, and Wessel van Woerden. Advanced lattice sieving on gpus, with tensor cores. Cryptology ePrint Archive, Report 2021/141, 2021. https://ia.cr/2021/141.
L ́eo Ducas. Shortest vector from lattice sieving: A few dimensions for free. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, pages 125–145, Cham, 2018. Springer International Publishing.
Masaharu Fukase and Kenji Kashiwabara. An accelerated algorithm for solving SVP based on statistical analysis. JIP, 23(1):67–80, 2015.
Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Tech- niques, French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 257–278. Springer, 2010.
C. Heckler and L. Thiele. Complexity analysis of a parallel lattice basis reduction algo- rithm. SIAM Journal on Computing, 27(5):1295–1302, 1998.
Jens Hermans, Michael Schneider, Johannes A. Buchmann, Frederik Vercauteren, and Bart Preneel. Parallel shortest lattice vector enumeration on graphics cards. In Daniel J. Bernstein and Tanja Lange, editors, Progress in Cryptology - AFRICACRYPT 2010, Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010. Proceedings, volume 6055 of Lecture Notes in Computer Science, pages 52–68. Springer, 2010.
J. Hoffstein, J. Pipher, and J.H. Silverman. An Introduction to Mathematical Cryptogra- phy. Undergraduate Texts in Mathematics. Springer New York, 2008.
Tsukasa Ishiguro, Shinsaku Kiyomoto, Yutaka Miyake, and Tsuyoshi Takagi. Parallel gauss sieve algorithm: Solving the svp challenge over a 128-dimensional ideal lattice. In Hugo Krawczyk, editor, Public-Key Cryptography – PKC 2014, pages 411–428, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 193–206. ACM, 1983.
Thijs Laarhoven and Artur Mariano. Progressive lattice sieving. In T. Lange and R. Steinwandt, editors, Post-Quantum Cryptography, Lecture Notes in Computer Science (includ- ing subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pages 292–311, Germany, 2018. Springer. 9th International Conference on Post-Quantum Cryptography (PQCrypto 2018), PQCrypto 2018 ; Conference date: 09-04-2018 Through 11-04-2018.
Christoph Ludwig. Practical Lattice Basis Sampling Reduction. PhD thesis, Technische Universit ̈at Darmstadt Universit ̈ats, 2005.
Yoshitatsu Matsuda, Tadanori Teruya, and Kenji Kashiwabara. Efficient estimation of number of short lattice vectors in search space under randomness assumption. In Keita Emura and Takaaki Mizuki, editors, Proceedings of the 6th on ASIA Public-Key Cryp- tography Workshop, APKC@AsiaCCS 2019, Auckland, New Zealand, July 8, 2019, pages 13–22. ACM, 2019.
Yoshitatsu Matsuda, Tadanori Teruya, and Kenji Kashiwabara. Efficient estimation of number of short lattice vectors in search space under randomness assumption. In Proceed- ings of the 6th on ASIA Public-Key Cryptography Workshop, APKC ’19, pages 13–22, New York, NY, USA, 2019. ACM.
Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2(2):181–207, 2008.
Claus-Peter Schnorr. Lattice reduction by random sampling and birthday methods. In Helmut Alt and Michel Habib, editors, STACS 2003, 20th Annual Symposium on The- oretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, volume 2607 of Lecture Notes in Computer Science, pages 145–156. Springer, 2003.
Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algo- rithms and solving subset sum problems. Math. Program., 66:181–199, 1994.
Tadanori Teruya, Kenji Kashiwabara, and Goichiro Hanaoka. Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part I, volume 10769 of Lecture Notes in Computer Science, pages 437–460. Springer, 2018.
The FPLLL development team. fplll, a lattice reduction library. https://github.com/fplll/fplll, 2016.
The G6K development team. G6K, the general sieve kernel. https://github.com/fplll/g6k, 2018.
Gilles Villard. Parallel lattice basis reduction. In ISSAC ’92, 1992.
ダウンロード
公開済
投稿日時: 2022-04-27 13:40:52 UTC
公開日時: 2022-05-02 09:20:43 UTC
ライセンス
Copyright（c）2022
柏原, 賢二
この作品は、Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Licenseの下でライセンスされています。
