DIMACS TR: 2008-12
A Parallel LLL using POSIX Threads
Authors: Werner Backes and Susanne Wetzel
ABSTRACT
In this paper we introduce a new parallel variant of the LLL lattice basis
reduction algorithm. Lattice theory and in particular lattice basis reduction
continues to play an integral role in cryptography. Not only does it provide
effective cryptanalysis tools but it is also believed to bring about new
cryptographic primitives that exhibit strong security even in the presence
of quantum computers. In theory, many aspects of lattices are already
well-understood. Yet, many practical aspects, like the performance of
lattice basis reduction algorithms, are still under investigation.
We introduce a new parallel lattice basis reduction algorithm that overcomes shortcomings of previously introduced algorithms. First and
foremost, our new algorithm is based on the Schnorr-Euchner algorithm and
as such is the first---to the best of our knowledge---to provide a parallel
implementation for the Schnorr-Euchner algorithm. Second, using POSIX threads
allows us to make effective use of today's multi-processor, multi-core
computer architecture. Developing in a shared memory setting allows us to
replace time consuming inter-process communication with synchronization points
(barriers) and locks (mutexes). Our implementation of the parallel LLL is
optimized for reducing high dimensional lattice bases with big entries that
would require a multi-precision floating-point arithmetic to approximate the
lattice basis if the original Schnorr-Euchner algorithm was used for the
reduction. The reduction of these lattice bases is of great interest, e.g.,
for cryptanalyzing RSA. In experiments with sparse and dense lattice bases,
experiments with our new parallel LLL show (compared to the non-parallel
algorithm) a speed-up factor of about 1.75 for the 2-thread and close to
factor 3 for the 4-thread version. The overhead of the parallel LLL
decreases with increasing dimension of the lattice basis to less than 10%
for the 2-thread and less than 15% for the 4-thread version.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2008/2008-12.pdf
DIMACS Home Page