TU Darmstadt / ULB / TUbiblio

Random Sampling for Short Lattice Vectors on Graphics Cards

Schneider, Michael ; Göttert, Norman
Hrsg.: Preneel, Bart ; Takagi, Tsuyoshi (2011)
Random Sampling for Short Lattice Vectors on Graphics Cards.
Nara, Japan
doi: 10.1007/978-3-642-23951-9_11
Konferenzveröffentlichung, Bibliographie

Kurzbeschreibung (Abstract)

We present a GPU implementation of the Simple Sampling Reduction (SSR) algorithm that searches for short vectors in lattices. SSR makes use of the famous BKZ algorithm. It complements an exhaustive search in a suitable search region to insert random, short vectors to the lattice basis. The sampling of short vectors can be executed in parallel. Our GPU implementation increases the number of sampled vectors per second from 5200 to more than 120, 000. With this we are the first to present a parallel implementation of SSR and we make use of the computing capability of modern graphics cards to enhance the search for short vectors even more.

Typ des Eintrags: Konferenzveröffentlichung
Erschienen: 2011
Herausgeber: Preneel, Bart ; Takagi, Tsuyoshi
Autor(en): Schneider, Michael ; Göttert, Norman
Art des Eintrags: Bibliographie
Titel: Random Sampling for Short Lattice Vectors on Graphics Cards
Sprache: Englisch
Publikationsjahr: September 2011
Verlag: Springer
(Heft-)Nummer: 6917
Buchtitel: Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011)
Reihe: LNCS
Veranstaltungsort: Nara, Japan
DOI: 10.1007/978-3-642-23951-9_11
Kurzbeschreibung (Abstract):

We present a GPU implementation of the Simple Sampling Reduction (SSR) algorithm that searches for short vectors in lattices. SSR makes use of the famous BKZ algorithm. It complements an exhaustive search in a suitable search region to insert random, short vectors to the lattice basis. The sampling of short vectors can be executed in parallel. Our GPU implementation increases the number of sampled vectors per second from 5200 to more than 120, 000. With this we are the first to present a parallel implementation of SSR and we make use of the computing capability of modern graphics cards to enhance the search for short vectors even more.

Freie Schlagworte: Secure Data;Lattice reduction, random sampling, SSR, BKZ
ID-Nummer: TUD-CS-2011-0191
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt
20 Fachbereich Informatik > Systemsicherheit
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra > Post-Quantum Kryptographie
LOEWE > LOEWE-Zentren
20 Fachbereich Informatik
LOEWE
Hinterlegungsdatum: 04 Aug 2016 15:08
Letzte Änderung: 17 Mai 2018 13:02
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen