Schneider, Michael ; Göttert, Norman
eds.: 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
Conference or Workshop Item
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.
Item Type: | Conference or Workshop Item |
---|---|
Erschienen: | 2011 |
Editors: | Preneel, Bart ; Takagi, Tsuyoshi |
Creators: | Schneider, Michael ; Göttert, Norman |
Type of entry: | Bibliographie |
Title: | Random Sampling for Short Lattice Vectors on Graphics Cards |
Language: | English |
Date: | September 2011 |
Publisher: | Springer |
Issue Number: | 6917 |
Book Title: | Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011) |
Series: | LNCS |
Event Location: | Nara, Japan |
DOI: | 10.1007/978-3-642-23951-9_11 |
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. |
Uncontrolled Keywords: | Secure Data;Lattice reduction, random sampling, SSR, BKZ |
Identification Number: | TUD-CS-2011-0191 |
Divisions: | 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra LOEWE > LOEWE-Zentren > CASED – Center for Advanced Security Research Darmstadt 20 Department of Computer Science > System Security Lab 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra > Post-Quantum Cryptography LOEWE > LOEWE-Zentren 20 Department of Computer Science LOEWE |
Date Deposited: | 04 Aug 2016 15:08 |
Last Modified: | 17 May 2018 13:02 |
PPN: | |
Export: | |
Suche nach Titel in: | TUfind oder in Google |
![]() |
Send an inquiry |
Options (only for editors)
![]() |
Show editorial Details |