[AD21] Martin Albrecht and Léo Ducas. “Lattice Attacks on NTRU and LWE: A History of Refinements”. In: Cryptology ePrint Archive: Report 2021/799 (2021).
[Ajt96] Miklós Ajtai. “Generating hard instances of lattice problems”. In: Symposium on Theory of Computing (STOC 1996). ACM. 1996, pp. 99–108.
[AKS01] Miklós Ajtai, Ravi Kumar, and Dandapani Sivakumar. “A sieve algorithm for the shortest lattice vector problem”. In: Symposium on Theory of Computing (STOC 2001). ACM. 2001, pp. 601–610.
[Alb+18] Martin R Albrecht et al. “Estimate all the {LWE, NTRU} schemes!” In: Security and Cryptography for Networks (SCN 2018). Vol. 11035. Lecture Notes in Computer Science. 2018, pp. 351–367.
[Alb+19] Martin Albrecht et al. “The general sieve kernel and new records in lattice reduction”. In: Advances in Cryptology–EUROCRYPT 2019. Vol. 11477. Lecture Notes in Computer Science. Springer. 2019, pp. 717–746.
[Bab86] László Babai. “On Lovász’ lattice reduction and the nearest lattice point problem”. In: Combinatorica 6.1 (1986), pp. 1–13.
[BBK19] Michael Burger, Christian Bischof, and Juliane Krämer. “p3Enum: A New Parameterizable and Shared-Memory Parallelized Shortest Vector Problem Solver”. In: Computational Science–ICCS 2019. Vol. 11540. Lecture Notes in Computer Science. Springer. 2019, pp. 535–542.
[BG73] Ake Björck and Gene H Golub. “Numerical methods for computing angles be- ˙ tween linear subspaces”. In: Mathematics of computation 27.123 (1973), pp. 579– 594.
[BN02] Alexander Barg and D Yu Nogin. “Bounds on packings of spheres in the Grassmann manifold”. In: IEEE Transactions on Information Theory 48.9 (2002), pp. 2450– 2454.
[Bre11] Murray R Bremner. Lattice basis reduction: An introduction to the LLL algorithm and its applications. CRC Press, 2011.
[BSW18] Shi Bai, Damien Stehlé, and Weiqiang Wen. “Measuring, Simulating and Exploiting the Head Concavity Phenomenon in BKZ”. In: Advances in Cryptology – ASIACRYPT 2018. Vol. 11272. Lecture Notes in Computer Science. Springer, 2018, pp. 369–404. DOI: 10.1007/978-3-030-03326-2_13.
[Cai00] Jin-Yi Cai. “The Complexity of Some Lattice Problems”. In: Algorithmic Number Theory. Ed. by Wieb Bosma. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000, pp. 1–32. ISBN: 978-3-540-44994-2.
[Che13] Yuanmi Chen. “Réduction de réseau et sécurité concrete du chiffrement completement homomorphe”. PhD thesis. Paris 7, 2013.
[Che16] Hao Chen. “A Measure Version of Gaussian Heuristic”. In: IACR Cryptology ePrint Archive: Report 2016/439 (2016).
[CN11] Yuanmi Chen and Phong Q Nguyen. “BKZ 2.0: Better lattice security estimates”. In: Advances in Cryptology–ASIACRYPT 2011. Vol. 7073. Lecture Notes in Computer Science. Springer. 2011, pp. 1–20.
[Det+10] Jérémie Detrey et al. “Accelerating lattice reduction with FPGAs”. In: International Conference on Cryptology and Information Security in Latin America. Springer. 2010, pp. 124–143.
[DG96] Peter Deutsch and Jean-Loup Gailly. Zlib compressed data format specification version 3.3. Tech. rep. RFC 1950, May, 1996.
[DS10] Öz6Kür Dagdelen and Michael Schneider. “Parallel enumeration of shortest lattice vectors”. In: Euro-Par 2010–Parallel Processing. Vol. 6272. Lecture Notes in Computer Science. Springer. 2010, pp. 211–222.
[DSW21] Léo Ducas, Marc Stevens, and Wessel van Woerden. “Advanced Lattice Sieving on GPUs, with Tensor Cores”. In: IACR ePrint 2021/141 (2021).
[Duc18] Léo Ducas. “Shortest vector from lattice sieving: A few dimensions for free”. In: Adavances in Cryptology–EUROCRYPT 2018. Vol. 10820. Lecture Notes in Computer Science. Springer. 2018, pp. 125–145.
[EAS98] Alan Edelman, Tomás A Arias, and Steven T Smith. “The geometry of algorithms with orthogonality constraints”. In: SIAM journal on Matrix Analysis and Applications 20.2 (1998), pp. 303–353.
[Fuj+21] Koichi Fujii et al. Solving Challenging Large Scale QAPs. eng. Tech. rep. 21-02. Takustr. 7, 14195 Berlin: ZIB, 2021.
[Gam+17] Gerald Gamrath et al. “SCIP-Jack—a solver for STP and variants with parallelization extensions”. In: Mathematical Programming Computation 9.2 (2017), pp. 231– 296. DOI: 10.1007/s12532-016-0114-x.
[GM03] Daniel Goldstein and Andrew Mayer. “On the equidistribution of Hecke points”. In: Forum Mathematicum. Vol. 15. 2. De Gruyter. 2003, pp. 165–190.
[GN08] Nicolas Gama and Phong Q Nguyen. “Predicting lattice reduction”. In: Advances in Cryptology–EUROCRYPT 2008. Vol. 4965. Lecture Notes in Computer Science. Springer. 2008, pp. 31–51.
[GNR10] Nicolas Gama, Phong Q. Nguyen, and Oded Regev. “Lattice Enumeration Using Extreme Pruning”. In: Advances in Cryptology – EUROCRYPT 2010. Ed. by Henri Gilbert. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 257–278. ISBN: 978-3-642-13190-5.
[GVL96] Gene H. Golub and Charles F. Van Loan. Matrix Computations. Forth. The Johns Hopkins University Press, 1996.
[Her+10] Jens Hermans et al. “Parallel shortest lattice vector enumeration on graphics cards”. In: Progress in Cryptology–AFRICACRYPT 2010. Vol. 6055. Lecture Notes in Computer Science. Springer. 2010, pp. 52–68.
[Her50] C. Hermite. “Extraits de lettres de M. Hermite à M. Jacobi sur différents objets de la théorie des nombres: Deuxième lettre”. In: Journal für die Reine und Angewandte Mathematik (1850), pp. 279–315.
[Jou12] Antoine Joux. “A tutorial on high performance computing applied to cryptanalysis (invited talk)”. In: Advances in Cryptology–EUROCRYPT 2012. Vol. 7237. Lecture Notes in Computer Science. Springer. 2012, pp. 1–7.
[Kan87] Ravi Kannan. “Minkowski’s convex body theorem and integer programming”. In: Mathematics of operations research 12.3 (1987), pp. 415–440.
[Kle00] Philip Klein. “Finding the closest lattice vector when it’s unusually close”. In: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. 2000, pp. 937–941.
[Kuo+11] Po-Chun Kuo et al. “Extreme Enumeration on GPU and in Clouds”. In: Cryptographic Hardware and Embedded Systems–CHES 2011. Vol. 6917. Lecture Notes in Computer Science. Springer. 2011, pp. 176–191.
[LLL82] Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. “Factoring polynomials with rational coefficients”. In: Mathematische Annalen 261.4 (1982), pp. 515–534.
[LLS90] J. C. Lagarias, H. W. Lenstra, and C. P. Schnorr. “Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice”. In: Combinatorica 10.4 (Dec. 1990), pp. 333–348. DOI: 10.1007/BF02128669. URL: https://doi.org/ 10.1007/BF02128669.
[Mic01] Daniele Micciancio. “The shortest vector in a lattice is hard to approximate to within some constant”. In: SIAM journal on Computing 30.6 (2001), pp. 2008– 2035. DOI: 10.1137/S0097539700373039.
[Mun+19] Lluís-Miquel Munguía et al. “Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs”. In: Computational Optimization and Applications 73.2 (June 2019), pp. 575–601. ISSN: 1573-2894. DOI: 10.1007/s10589-019-00074-0. URL: https://doi.org/10.1007/s10589-019-00074-0.
[MV10] Daniele Micciancio and Panagiotis Voulgaris. “Faster exponential time algorithms for the shortest vector problem”. In: Symposium on Discrete Algorithms (SODA 2010). ACM-SIAM. 2010, pp. 1468–1480.
[Ngu09] Phong Q Nguyen. “Hermite’s constant and lattice algorithms”. In: The LLL Algorithm. Springer, 2009, pp. 19–69.
[Pei16] Chris Peikert. “A Decade of Lattice Cryptography”. In: Foundations and Trends in Theoretical Computer Science 10.4 (2016), pp. 283–424. ISSN: 1551-305X. DOI: 10.1561/0400000074. URL: http://dx.doi.org/10.1561/0400000074.
[Poh87] Michael Pohst. “A modification of the LLL reduction algorithm”. In: Journal of Symbolic Computation 4.1 (1987), pp. 123–127.
[PSZ21] Simon Pohmann, Marc Stevens, and Jens Zumbrägel. “Lattice Enumeration on GPUs for fplll”. In: IACR ePrint 2021/430 (2021).
[Ral+18] Ted Ralphs et al. “Parallel Solvers for Mixed Integer Linear Optimization”. In: Handbook of Parallel Constraint Reasoning. Ed. by Youssef Hamadi and Lakhdar Sais. Cham: Springer International Publishing, 2018, pp. 283–336. ISBN: 978-3- 319-63516-3. DOI: 10.1007/978-3-319-63516-3{\_}8. URL: https://doi.org/ 10.1007/978-3-319-63516-3_8.
[RSK21] Daniel Rehfeldt, Yuji Shinano, and Thorsten Koch. “SCIP-Jack: An Exact High Performance Solver for Steiner Tree Problems in Graphs and Related Problems”. In: Modeling, Simulation and Optimization of Complex Processes HPSC 2018. Ed. by Hans Georg Bock et al. Cham: Springer International Publishing, 2021, pp. 201– 223. ISBN: 978-3-030-55240-4.
[SBH18] Yuji Shinano, Timo Berthold, and Stefan Heinz. “ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers”. In: Optimization Methods and Software 33.3 (2018), pp. 530–539. DOI: 10 . 1080/10556788.2018.1428602. eprint: https://doi.org/10.1080/10556788. 2018.1428602. URL: https://doi.org/10.1080/10556788.2018.1428602.
[Sch03] Claus Peter Schnorr. “Lattice reduction by random sampling and birthday methods”. In: Symposium on Theoretical Aspects of Computer Science (STACS 2003). Vol. 2607. Lecture Notes in Computer Science. Springer. 2003, pp. 145–156.
[Sch+10] Michael Schneider et al. “SVP challenge (2010)”. In: URL: http://latticechallenge.org/svpchallenge (2010).
[Sch87] Claus-Peter Schnorr. “A hierarchy of polynomial time lattice basis reduction algorithms”. In: Theoretical computer science 53.2-3 (1987), pp. 201–224.
[Sch92] Claus-Peter Schnorr. Block Korkin-Zolotarev bases and successive minima. International Computer Science Institute, 1992.
[Sci] SCIP: Solving Constraint Integer Programs. http://scip.zib.de/.
[SE94] Claus-Peter Schnorr and Martin Euchner. “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”. In: Mathematical programming 66 (1994), pp. 181–199.
[Shi+11] Yuji Shinano et al. “ParaSCIP—a parallel extension of SCIP”. In: Competence in High Performance Computing 2010. Springer, 2011, pp. 135–148.
[Shi+16] Yuji Shinano et al. “Solving Open MIP Instances with ParaSCIP on Supercomputers Using up to 80,000 Cores”. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). Los Alamitos, CA, USA: IEEE Computer Society, 2016, pp. 770–779.
[Shi+18a] Yuji Shinano et al. “FiberSCIP—a shared memory parallelization of SCIP”. In: INFORMS Journal on Computing 30.1 (2018), pp. 11–30.
[Shi+18b] Yuji Shinano et al. “FiberSCIP—A Shared Memory Parallelization of SCIP”. In: INFORMS Journal on Computing 30.1 (2018), pp. 11–30. DOI: 10 . 1287 / ijoc . 2017.0762. eprint: https://doi.org/10.1287/ijoc.2017.0762. URL: https://doi.org/10.1287/ijoc.2017.0762.
[Sho94] Peter W. Shor. “Algorithms for quantum computation: Discrete logarithms and factoring”. In: Symposium on Foundations of Computer Science (FOCS 1994). IEEE, 1994, pp. 124–134.
[SN] The National Institute of Standards and Technology (NIST). “Post-Quantum Cryptography”. URL: https : / / csrc . nist . gov / projects / post - quantum - cryptography/post-quantum-cryptography-standardization.
[SRG19] Yuji Shinano, Daniel Rehfeldt, and Tristan Gally. “An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ug[SCIP-*,*]-Libraries”. In: 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 2019, pp. 530–541. DOI: 10.1109/IPDPSW.2019.00095.
[SRK19] Yuji Shinano, Daniel Rehfeldt, and Thorsten Koch. “Building Optimal Steiner Trees on Supercomputers by Using up to 43,000 Cores”. In: Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2019. Vol. 11494. 2019, pp. 529–539. DOI: 10.1007/978-3-030-19212-9_35.
[Tat+20] Nariaki Tateiwa et al. “Massive parallelization for finding shortest lattice vectors based on ubiquity generator framework”. In: SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE. 2020, pp. 1–15.
[Tat+21] Nariaki Tateiwa et al. “CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems “in press””. In: 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC). IEEE. 2021.
[The16] The FPLLL development team. “fplll, a lattice reduction library”. 2016. URL: https://github.com/fplll/fplll.
[TKH18] Tadanori Teruya, Kenji Kashiwabara, and Goichiro Hanaoka. “Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem”. In: Public Key Cryptography (PKC 2018). Vol. 10769. Lecture Notes in Computer Science. Springer. 2018, pp. 437–460.
[Ug] UG: Ubiquity Generator framework. http://ug.zib.de/.
[Yas21] Masaya Yasuda. “A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge”. In: International Symposium on Mathematics, Quantum Theory, and Cryptography. Springer. 2021, pp. 189–207.
[YD17] Yang Yu and Léo Ducas. “Second order statistical behavior of LLL and BKZ”. In: Selected Areas in Cryptography (SAC 2017). Vol. 10719. Lecture Notes in Computer Science. Springer. 2017, pp. 3–22.
[YNY20] Masaya Yasuda, Satoshi Nakamura, and Junpei Yamaguchi. “Analysis of DeepBKZ reduction for finding short lattice vectors”. In: Designs, Codes and Cryptography 88 2020), pp. 2077–2100.
[YY17] Junpei Yamaguchi and Masaya Yasuda. “Explicit formula for Gram-Schmidt vectors in LLL with deep insertions and its applications”. In: Number-Theoretic Methods in Cryptology (NuTMiC 2017). Vol. 10737. Lecture Notes in Computer Science. Springer. 2017, pp. 142–160.
[YY19] Masaya Yasuda and Junpei Yamaguchi. “A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths”. In: Designs, Codes and Cryptography 87 (11 2019), pp. 2489–2505.
論文の公開元へ
