TU Darmstadt / ULB / TUbiblio

Random Sampling for Short Lattice Vectors on Graphics Cards

Schneider, Michael and Göttert, Norman
Preneel, Bart and Takagi, Tsuyoshi (eds.) (2011):
Random Sampling for Short Lattice Vectors on Graphics Cards.
In: Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011), Springer, Nara, Japan, In: LNCS, 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 and Takagi, Tsuyoshi
Creators: Schneider, Michael and Göttert, Norman
Title: Random Sampling for Short Lattice Vectors on Graphics Cards
Language: ["languages_typename_1" not defined]
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.

Title of Book: Workshop on Cryptographic Hardware and Embedded Systems 2011 (CHES 2011)
Series Name: LNCS
Number: 6917
Publisher: Springer
Uncontrolled Keywords: Secure Data;Lattice reduction, random sampling, SSR, BKZ
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
Event Location: Nara, Japan
Date Deposited: 04 Aug 2016 15:08
DOI: 10.1007/978-3-642-23951-9_11
Identification Number: TUD-CS-2011-0191
Export:

Optionen (nur für Redakteure)

View Item View Item