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.10.2018-31.10.2018)
doi: 10.1109/CSE.2018.00012
Konferenzveröffentlichung, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Konferenzveröffentlichung |
|---|---|
| Erschienen: | 2018 |
| Autor(en): | Burger, Michael ; Bischof, Christian ; Calotoiu, Alexandru ; Wunderer, Thomas ; Wolf, Felix |
| Art des Eintrags: | Bibliographie |
| Titel: | Exploring the Performance Envelope of the LLL Algorithm |
| Sprache: | Englisch |
| Publikationsjahr: | 27 Dezember 2018 |
| Verlag: | IEEE |
| Buchtitel: | Proceedings: 21st IEEE International Conference on Computational Science and Engineering: CSE 2018 |
| Veranstaltungstitel: | 21st IEEE International Conference on Computational Science and Engineering |
| Veranstaltungsort: | Bucharest, Romania |
| Veranstaltungsdatum: | 29.10.2018-31.10.2018 |
| DOI: | 10.1109/CSE.2018.00012 |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Primitives, P1, DFG|320898076, DFG, 320898076 |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra 20 Fachbereich Informatik > Parallele Programmierung 20 Fachbereich Informatik > Scientific Computing DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche Profilbereiche Profilbereiche > Cybersicherheit (CYSEC) Zentrale Einrichtungen Zentrale Einrichtungen > Hochschulrechenzentrum (HRZ) Zentrale Einrichtungen > Hochschulrechenzentrum (HRZ) > Hochleistungsrechner DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
| Hinterlegungsdatum: | 12 Sep 2018 12:01 |
| Letzte Änderung: | 29 Feb 2024 15:31 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum