{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T10:10:25Z","timestamp":1753438225031,"version":"3.40.5"},"reference-count":36,"publisher":"Wiley","license":[{"start":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T00:00:00Z","timestamp":1609804800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Scientific Programming"],"published-print":{"date-parts":[[2021,1,5]]},"abstract":"<jats:p>Hard Lattice problems are assumed to be one of the most promising problems for generating cryptosystems that are secure in quantum computing. The shortest vector problem (SVP) is one of the most famous lattice problems. In this paper, we present three improvements on GPU-based parallel algorithms for solving SVP using the classical enumeration and pruned enumeration. There are two improvements for preprocessing: we use a combination of randomization and the Gaussian heuristic to expect a better basis that leads rapidly to a shortest vector and we expect the level on which the exchanging data between CPU and GPU is optimized. In the third improvement, we improve GPU-based implementation by generating some points in GPU rather than in CPU. We used NVIDIA GeForce GPUs of type GTX 1060 6G. We achieved a significant improvement upon Hermans\u2019s improvement. The improvements speed up the pruned enumeration by a factor of almost 2.5 using a single GPU. Additionally, we provided an implementation for multi-GPUs by using two GPUs. The results showed that our algorithm of enumeration is scalable since the speedups achieved using two GPUs are almost faster than Hermans\u2019s improvement by a factor of almost 5. The improvements also provided a high speedup for the classical enumeration. The speedup achieved using our improvements and two GPUs on a challenge of dimension 60 is almost faster by factor 2 than Correia\u2019s parallel implementation using a dual-socket machine with 16 physical cores and simultaneous multithreading technology.<\/jats:p>","DOI":"10.1155\/2021\/8852497","type":"journal-article","created":{"date-parts":[[2021,1,5]],"date-time":"2021-01-05T20:27:19Z","timestamp":1609878439000},"page":"1-13","source":"Crossref","is-referenced-by-count":1,"title":["Three Strategies for Improving Shortest Vector Enumeration Using GPUs"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5464-2485","authenticated-orcid":true,"given":"Mohamed S.","family":"Esseissah","sequence":"first","affiliation":[{"name":"Computer Science Division, Mathematics Department, Faculty of Science, Ain Shams University, Cairo, Egypt"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9016-2705","authenticated-orcid":true,"given":"Ashraf","family":"Bhery","sequence":"additional","affiliation":[{"name":"Computer Science Division, Mathematics Department, Faculty of Science, Ain Shams University, Cairo, Egypt"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0937-8849","authenticated-orcid":true,"given":"Sameh S.","family":"Daoud","sequence":"additional","affiliation":[{"name":"Computer Science Division, Mathematics Department, Faculty of Science, Ain Shams University, Cairo, Egypt"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8137-7939","authenticated-orcid":true,"given":"Hatem M.","family":"Bahig","sequence":"additional","affiliation":[{"name":"Computer Science Division, Mathematics Department, Faculty of Science, Ain Shams University, Cairo, Egypt"}]}],"member":"311","reference":[{"first-page":"10","article-title":"The shortest vector problem in L2 is NP-hard for randomized reductions","author":"M. Ajtai","key":"1"},{"key":"2","unstructured":"van Emde BoasP.Another NP-complete problem and the complexity of computing short vectors in a lattice1981Amsterdam, NetherlandsDepartment of Mathmatics, University of AmsterdamTecnical Report"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33027-8_31"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/2724713"},{"first-page":"131","article-title":"Lattice-based cryptography","author":"O. Regev","key":"5"},{"first-page":"112","article-title":"Public-key cryptosystems from lattice reduction problems","author":"O. Goldreich","key":"6"},{"first-page":"267","article-title":"NTRU: a ring-based public key cryptosystem","author":"J. Hoffstein","key":"7"},{"first-page":"319","article-title":"Better key sizes (and attacks) for LWE-based encryption","author":"R. Lindner","key":"8"},{"first-page":"84","article-title":"On lattices, learning with errors, random linear codes, and cryptography","author":"O. Regev","key":"9"},{"issue":"4","key":"10","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF01457454","article-title":"Factoring polynomials with rational coefficients","volume":"261","author":"A. K. Lenstra","year":"1982","journal-title":"Mathematische Annalen"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_7"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374408"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_31"},{"first-page":"68","article-title":"Lattice basis reduction: improved practical algorithms and solving subset sum problems","author":"C.-P. Schnorr","key":"14"},{"first-page":"1","article-title":"Attacking the Chor-Rivest cryptosystem by improved lattice reduction","author":"C.-P. Schnorr","key":"15"},{"first-page":"193","article-title":"Improved algorithms for integer programming and related lattice problems","author":"R. Kannan","key":"16"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1137\/100811970"},{"first-page":"601","article-title":"A sieve algorithm for the shortest lattice vector problem","author":"M. Ajtai","key":"18"},{"issue":"170","key":"19","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1090\/S0025-5718-1985-0777278-8","article-title":"Improved methods for calculating vectors of short length in a lattice, including a complexity analysis","volume":"44","author":"U. Fincke","year":"1985","journal-title":"Mathematics of Computation"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_10"},{"volume-title":"NTL: A Library for Doing Number Theory","year":"2001","author":"V. Shoup","key":"21"},{"article-title":"fpLLL-4.0, a floating-point LLL implementation","year":"2017","author":"M. Albrecht","key":"22"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03869-3_88"},{"first-page":"27","article-title":"Improving the parallel Schnorr-Euchner LLL algorithm","author":"B. Werner","key":"25"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14712-8_8"},{"first-page":"211","article-title":"Parallel enumeration of shortest lattice vectors","author":"\u00d6. Dagdelen","key":"27"},{"first-page":"52","article-title":"Parallel shortest lattice vector enumeration on graphics cards","author":"J. Hermans","key":"28"},{"key":"29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23951-9_12"},{"first-page":"596","article-title":"Parallel improved Schnorr-Euchner enumeration se++ for the CVP and SVP","author":"F. Correia","key":"30"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-018-2840-5"},{"first-page":"1","article-title":"Accelerating NTRU based homomorphic encryption using gpus","author":"W. Dai","key":"32"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2961091"},{"key":"34","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"S. D. Galbraith","year":"2012"},{"key":"35","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4939-1711-2","volume-title":"An Introduction to Mathematical Cryptography","author":"J. Hoffstein","year":"2014"},{"volume-title":"Professional CUDA C Programming","year":"2014","author":"J. Cheng","key":"36"}],"container-title":["Scientific Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/8852497.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/8852497.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/sp\/2021\/8852497.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T23:24:10Z","timestamp":1697498650000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/sp\/2021\/8852497\/"}},"subtitle":[],"editor":[{"given":"Jianping","family":"Gou","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,1,5]]},"references-count":36,"alternative-id":["8852497","8852497"],"URL":"https:\/\/doi.org\/10.1155\/2021\/8852497","relation":{},"ISSN":["1875-919X","1058-9244"],"issn-type":[{"type":"electronic","value":"1875-919X"},{"type":"print","value":"1058-9244"}],"subject":[],"published":{"date-parts":[[2021,1,5]]}}}