Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/38808
Título: | Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP |
Autor(es): | Correia, Fábio José Gonçalves Mariano, Artur Miguel Matos Proença, Alberto José Bischof, Christian Agrell, Erik |
Data: | 2016 |
Editora: | IEEE |
Revista: | Euromicro Conference on Parallel Distributed and Network-Based Processing |
Resumo(s): | The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date. |
Tipo: | Artigo em ata de conferência |
URI: | https://hdl.handle.net/1822/38808 |
ISBN: | 9781467387750 |
DOI: | 10.1109/PDP.2016.95 |
ISSN: | 1066-6192 |
Arbitragem científica: | yes |
Acesso: | Acesso aberto |
Aparece nas coleções: | DI/CCTC - Artigos (papers) |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
PID4026887.pdf | 402,14 kB | Adobe PDF | Ver/Abrir |