Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/78135
Título: | Optimized voronoi-based algorithms for parallel shortest vector computation |
Autor(es): | Mariano, Artur Cabeleira, Filipe Santos, Luís Paulo Falcão, Gabriel |
Palavras-chave: | cryptanalysis parallel computing |
Data: | 2022 |
Editora: | Taylor & Francis |
Resumo(s): | This chapter addresses Voronoi cell-based algorithms, solving the Shortest Vector Problem, a fundamental challenge in lattice-based cryptanalysis. Several optimizations reduce the original algorithm's execution time. The algorithm suitability for parallel execution on both CPUs and GPUs is also shown. Optimizations are based on pruning, avoiding computations that will not improve the solution. The pruning criteria is related to the target vectors norm relative to the current best solution vector norm. Speedups up to 69× are observed. With a pre-process sorting step, which requires storing the norm ordered target vectors and therefore significantly more memory, speedup increases to 77×. On the parallel processing side, the optimized algorithm exhibits linear scalability on a CPU with up to 28 threads and keeps scaling, at a lower rate, with Simultaneous Multi-Threading up to 56 threads. The lack of support for efficient threads synchronization in GPUs precludes a scalable implementation of the pruning optimization. A parallel GPU version of the non-optimized algorithm is demonstrated to be competitive with the parallel non optimized CPU version, although the latter outperforms the former for 56 threads. GPUs are expected to outperform CPUs for higher lattice dimensions; this cannot be experimentally verified due to the limited memory available on current GPUs. |
Tipo: | Capítulo de livro |
URI: | https://hdl.handle.net/1822/78135 |
e-ISBN: | 9781003155799 |
DOI: | 10.1201/9781003155799-4 |
Versão da editora: | https://www.taylorfrancis.com/chapters/edit/10.1201/9781003155799-4/optimized-voronoi-based-algorithms-parallel-shortest-vector-computation-artur-mariano-filipe-cabeleira-lu%C3%ADs-paulo-santos-gabriel-falc%C3%A3o |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Voronoi_BookChapter (1).pdf | 1,2 MB | Adobe PDF | Ver/Abrir |
Este trabalho está licenciado sob uma Licença Creative Commons