Burger, Michael ; Bischof, Christian ; Calotoiu, Alexandru ; Wunderer, Thomas ; Wolf, Felix (2018)
Exploring the Performance Envelope of the LLL Algorithm.
21st IEEE International Conference on Computational Science and Engineering. Bucharest, Romania (29.-31.10.2018)
doi: 10.1109/CSE.2018.00012
Conference or Workshop Item, Bibliographie
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.
| Item Type: | Conference or Workshop Item |
|---|---|
| Erschienen: | 2018 |
| Creators: | Burger, Michael ; Bischof, Christian ; Calotoiu, Alexandru ; Wunderer, Thomas ; Wolf, Felix |
| Type of entry: | Bibliographie |
| Title: | Exploring the Performance Envelope of the LLL Algorithm |
| Language: | English |
| Date: | 27 December 2018 |
| Publisher: | IEEE |
| Book Title: | Proceedings: 21st IEEE International Conference on Computational Science and Engineering: CSE 2018 |
| Event Title: | 21st IEEE International Conference on Computational Science and Engineering |
| Event Location: | Bucharest, Romania |
| Event Dates: | 29.-31.10.2018 |
| DOI: | 10.1109/CSE.2018.00012 |
| 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. |
| Uncontrolled Keywords: | Primitives, P1, DFG|320898076, DFG, 320898076 |
| Divisions: | 20 Department of Computer Science 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra 20 Department of Computer Science > Parallel Programming 20 Department of Computer Science > Scientific Computing DFG-Collaborative Research Centres (incl. Transregio) DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres Profile Areas Profile Areas > Cybersecurity (CYSEC) Zentrale Einrichtungen Zentrale Einrichtungen > University IT-Service and Computing Centre (HRZ) Zentrale Einrichtungen > University IT-Service and Computing Centre (HRZ) > Hochleistungsrechner DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments |
| Date Deposited: | 12 Sep 2018 12:01 |
| Last Modified: | 29 Feb 2024 15:31 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Send an inquiry |
Options (only for editors)
 |
Show editorial Details |
Drucken
Impressum