Title
Exploring the Performance Envelope of the LLL Algorithm
Abstract
In this paper, we investigate two implementations of the LLL lattice basis reduction algorithm in the popular NTL and fplll libraries, which helps to assess the security of lattice-based cryptographic schemes. The work has two main contributions: First, we present a novel method to develop performance models and use the unpredictability of LLL's behavior in dependence of the structure of the input lattice as an illustrative example. The model generation approach is based on profiled training measurements of the code and the final runtime performance models are constructed by an extended version of the open source tool Extra-P by systematic consideration of a variety of hypothesis functions via shared-memory parallelized simulated annealing. We employ three kinds of lattice bases for our tests: Random lattice bases of Goldstein-Mayer form with linear and quadratic increase in the bit length of their entries and NTRU-like matrices. The performance models derived show a very good fit to the experimental data and a high variety in their range of complexity which we compare to predictions by theoretical upper bounds and previous average-case estimates. The modeling principles demonstrated by the example of the use case LLL are directly applicable to other algorithms in cryptography and general serial and parallel algorithms. Second, we also evaluate the common approach of estimating the runtime on the basis of the number of floating point operations or bit operations executed within an algorithm and combining them with theoretical assumptions about the executing processor (clock rate, operations per tick). Our experiments show that this approach leads to unreliable estimates for the runtime.
Year
DOI
Venue
2018
10.1109/CSE.2018.00012
2018 IEEE International Conference on Computational Science and Engineering (CSE)
Keywords
Field
DocType
performance models, model fitting, parallel simulated annealing, OpenMP
Simulated annealing,Data modeling,Parallel algorithm,Computer science,Floating point,Cryptography,Algorithm,Quadratic equation,Clock rate,Lattice reduction
Conference
ISSN
ISBN
Citations 
1949-0828
978-1-5386-7650-9
0
PageRank 
References 
Authors
0.34
6
5
Name
Order
Citations
PageRank
Michael Burger163.92
Christian H. Bischof2977169.63
Alexandru Calotoiu3798.04
Thomas Wunderer400.34
Felix Wolf55712.00