CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Parallel Improved Schnorr-Euchner Enumeration SE++ for the CVP and SVP

Fabio Correia ; Artur Mariano ; Alberto Proenca ; Christian Bischof ; Erik Agrell (Institutionen för signaler och system, Kommunikationssystem)
24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP 2016, Heraklion, Crete, Greece, 17-19 February 2016 p. 596-603. (2016)
[Konferensbidrag, refereegranskat]

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.



Denna post skapades 2016-07-11. Senast ändrad 2016-10-05.
CPL Pubid: 239240

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för signaler och system, Kommunikationssystem

Ämnesområden

Signalbehandling

Chalmers infrastruktur