TU Darmstadt / ULB / TUbiblio

Random Sampling for Short Lattice Vectors on Graphics Cards

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 Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details