Projects per year
Abstract
NonCentered Discrete Gaussian sampling is a fundamental building block in many latticebased constructions in cryptography, such as signature and identitybased encryption schemes. On the one hand, the centerdependent approaches, e.g. cumulative distribution tables (CDT), KnuthYao, the alias method, discrete Zigurat and their variants, are the fastest known algorithms to sample from a discrete Gaussian distribution. However, they use a relatively large precomputed table for each possible real center in [0,1)[0,1) making them impracticable for noncentered discrete Gaussian sampling. On the other hand, rejection sampling allows to sample from a discrete Gaussian distribution for all real centers without prohibitive precomputation cost but needs costly floatingpoint arithmetic and several trials per sample. In this work, we study how to reduce the number of centers for which we have to precompute tables and propose a noncentered CDT algorithm with practicable size of precomputed tables as fast as its centered variant. Finally, we provide some experimental results for our opensource C++ implementation indicating that our sampler increases the rate of Peikert’s algorithm for sampling from arbitrary lattices (and cosets) by a factor 3 with precomputation storage up to 6.2 MB.
Original language  English 

Title of host publication  Applied Cryptography and Network Security 
Subtitle of host publication  ACNS 2017 
Publisher  Springer 
Pages  319 
Number of pages  17 
Volume  10355 
ISBN (Electronic)  9783319612041 
ISBN (Print)  9783319612034 
DOIs  
Publication status  Published  2017 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer, Cham 
Volume  10355 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Projects
 2 Finished

Multilinear Maps in Cryptography
Paterson, K.
Eng & Phys Sci Res Council EPSRC
31/01/14 → 30/01/17
Project: Research