nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)

verfasst von : Errui He, Tianyu Xu, Mengsi Wu, Jiageng Chen, Shixiong Yao, Pei Li

Erschienen in: Blockchain Technology and Emerging Applications

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Lattice-based encryption schemes derive their security from the presumed complexity of solving the Shortest Vector Problem (SVP) within the lattice structure. Numerous algorithms have been proposed to address the SVP, targeting both exact and approximate solutions. However, it is noteworthy that the time complexity associated with these algorithms predominantly exceeds polynomial bounds. This paper succinctly delineates these algorithms while providing a comprehensive summary of existing parallel implementations of sieving and enumeration methods. Furthermore, it introduces distinguished instances from the Hall of Fame of the SVP challenge.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fuzz Testing of UAV Configurations Based on Evolutionary Algorithm

Nächstes Kapitel PSWS: A Private Support-Weighted Sum Protocol for Blockchain-Based E-Voting Systems

Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 99–108 (1996)

Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 601–610 (2001)

Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The General Sieve Kernel and New Records in Lattice Reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 717–746. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_25CrossRef

Andrzejczak, M., Gaj, K.: A Multiplatform Parallel Approach for Lattice Sieving Algorithms. In: Qiu, M. (ed.) ICA3PP 2020. LNCS, vol. 12452, pp. 661–680. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60245-1_45CrossRef

Aono, Y., Nguyen, P.Q., Seito, T., Shikata, J.: Lower Bounds on Lattice Enumeration with Extreme Pruning. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 608–637. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_21CrossRef

Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved Progressive BKZ Algorithms and Their Precise Cost Estimation by Sharp Simulator. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 789–819. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_30CrossRef

Bai, S., Laarhoven, T., Stehlé, D.: Tuple lattice sieving. LMS J. Comput. Math. 19(A), 146–162 (2016)

Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms,pp. 10–24. SIAM (2016)

Burger, M., Bischof, C., Krämer, J.: A new parallelization for p3enum and parallelized generation of optimized pruning functions. In: 2019 International Conference on High Performance Computing and Simulation (HPCS), pp. 931–939. IEEE (2019)

10.

Burger, M., Bischof, C., Krämer, J.: p3Enum: A new parameterizable and shared-memory parallelized shortest vector problem solver. In: Rodrigues, J.M.F., Cardoso, P.J.S., Monteiro, J., Lam, R., Krzhizhanovskaya, V.V., Lees, M.H., Dongarra, J.J., Sloot, P.M.A. (eds.) ICCS 2019. LNCS, vol. 11540, pp. 535–542. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22750-0_48CrossRef

11.

Correia, F., Mariano, A., Proenca, A., Bischof, C., Agrell, E.: Parallel improved schnorr-euchner enumeration SE++ for the CVP and SVP. In: 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pp. 596–603. IEEE (2016)

12.

Dagdelen, Ö., Schneider, M.: Parallel Enumeration of Shortest Lattice Vectors. In: D’Ambra, P., Guarracino, M., Talia, D. (eds.) Euro-Par 2010. LNCS, vol. 6272, pp. 211–222. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15291-7_21CrossRef

13.

Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 125–145. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_5CrossRef

14.

Ducas, L., Stevens, M., van Woerden, W.: Advanced Lattice Sieving on GPUs, with Tensor Cores. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 249–279. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_9CrossRef

15.

Esseissah, M.S., Bhery, A., Daoud, S.S., Bahig, H.M.: Three strategies for improving shortest vector enumeration using GPUS. Sci. Program. 2021, 1–13 (2021)

16.

Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44(170), 463–471 (1985)MathSciNetCrossRef

17.

Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_13CrossRef

18.

Ghasemmehdi, A., Agrell, E.: Faster recursions in sphere decoding. IEEE Trans. Inf. Theory 57(6), 3530–3536 (2011)MathSciNetCrossRef

19.

Hermans, J., Schneider, M., Buchmann, J., Vercauteren, F., Preneel, B.: Parallel shortest lattice vector enumeration on graphics cards. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 52–68. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12678-9_4CrossRef

20.

Ishiguro, T., Kiyomoto, S., Miyake, Y., Takagi, T.: Parallel gauss sieve algorithm: solving the SVP challenge over a 128-dimensional ideal lattice. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 411–428. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_24CrossRef

21.

Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing, pp. 193–206 (1983)

22.

Kuo, P.-C., Schneider, M., Dagdelen, Ö., Reichelt, J., Buchmann, J., Cheng, C.-M., Yang, B.-Y.: Extreme enumeration on GPU and in clouds. In: Preneel, B., Takagi, T. (eds.) Extreme enumeration on GPU and in clouds. LNCS, vol. 6917, pp. 176–191. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23951-9_12CrossRef

23.

Laarhoven, T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 3–22. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_1CrossRef

24.

Laarhoven, T., Mariano, A.: Progressive lattice sieving. In: Lange, T., Steinwandt, R. (eds.) Progressive lattice sieving. LNCS, vol. 10786, pp. 292–311. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-79063-3_14CrossRef

25.

Laarhoven, T., Mosca, M., van de Pol, J.: Solving the shortest vector problem in lattices faster using quantum search. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 83–101. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38616-9_6CrossRef

26.

Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische annalen 261(ARTICLE), 515–534 (1982)

27.

Loyer, J., Chailloux, A.: Classical and quantum 3 and 4-sieves to solve SVP with low memory. Cryptology ePrint Archive (2023)

28.

Mariano, A., Bischof, C., Laarhoven, T.: Parallel (probable) lock-free hash sieve: a practical sieving algorithm for the SVP. In: 2015 44th International Conference on Parallel Processing, pp. 590–599. IEEE (2015)

29.

Mariano, A., Laarhoven, T., Bischof, C.: A parallel variant of lDSieve for the SVP on lattices. In: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), pp. 23–30. IEEE (2017)

30.

Mariano, A., Timnat, S., Bischof, C.: Lock-free gausssieve for linear speedups in parallel high performance SVP calculation. In: 2014 IEEE 26th International Symposium on Computer Architecture and High Performance Computing, pp. 278–285. IEEE (2014)

31.

Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1468–1480. SIAM (2010)

32.

Michael, S., Nicolas, G.: SVP Challenge (2010). https://www.latticechallenge.org/SVP-challenge/

33.

Milde, B., Schneider, M.: A parallel implementation of gausssieve for the shortest vector problem in lattices. In: Malyshkin, V. (ed.) PaCT 2011. LNCS, vol. 6873, pp. 452–458. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23178-0_40CrossRef

34.

Mukhopadhyay, P.: Faster provable sieving algorithms for the shortest vector problem and the closest vector problem on lattices in \(l_{p}\) norm. Algorithms 14(12), 362 (2021)CrossRef

35.

Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptology 2(2), 181–207 (2008)MathSciNetCrossRef

36.

Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM Sigsam Bulletin 15(1), 37–44 (1981)CrossRef

37.

Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)MathSciNetCrossRef

38.

Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-49264-X_1CrossRef

39.

Tateiwa, N., 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, pp. 1–15. IEEE (2020)

40.

Wang, L., Wang, Y., Wang, B.: A trade-off SVP-solving strategy based on a sharper PNJ-BKZ simulator. In: Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pp. 664–677 (2023)

41.

Wang, X., Liu, M., Tian, C., Bi, J.: Improved nguyen-vidick heuristic sieve algorithm for shortest vector problem. In: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, pp. 1–9 (2011)

42.

Xia, W., Wang, L., Gu, D., Wang, B., et al.: Improved progressive BKZ with lattice sieving. Cryptology ePrint Archive (2022)

43.

Schnorr, C.P., Hörner, H.H.: Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-49264-X_1CrossRef

44.

Yasuda, M.: A survey of solving SVP algorithms and recent strategies for solving the SVP challenge. In: Takagi, T., Wakayama, M., Tanaka, K., Kunihiro, N., Kimoto, K., Ikematsu, Y. (eds.) A survey of solving SVP algorithms and recent strategies for solving the svp challenge. MI, vol. 33, pp. 189–207. Springer, Singapore (2021). https://doi.org/10.1007/978-981-15-5191-8_15CrossRef

45.

Zhang, F., Pan, Y., Hu, G.: A Three-level sieve algorithm for the shortest vector problem. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) A three-level sieve algorithm for the shortest vector problem. LNCS, vol. 8282, pp. 29–47. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43414-7_2CrossRef

Titel: A Survey of Algorithms for Addressing the Shortest Vector Problem (SVP)
verfasst von: Errui He
Tianyu Xu
Mengsi Wu
Jiageng Chen
Shixiong Yao
Pei Li
Verlag: Springer Nature Switzerland
Buch: Blockchain Technology and Emerging Applications
Print ISBN: 978-3-031-60036-4

Electronic ISBN: 978-3-031-60037-1

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-60037-1_4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner