A New Discrete Gaussian Sampler over Orthogonal Lattices

Dianyan XIAO  Yang YU  Jingguo BI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.11   pp.1880-1887
Publication Date: 2018/11/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.1880
Type of Manuscript: PAPER
Category: Cryptography and Information Security
discrete Gaussian,  rejection sampling,  dynamic programming,  orthogonal lattice,  

Full Text: PDF(984.3KB)
>>Buy this Article

Discrete Gaussian is a cornerstone of many lattice-based cryptographic constructions. Aiming at the orthogonal lattice of a vector, we propose a discrete Gaussian rejection sampling algorithm, by modifying the dynamic programming process for subset sum problems. Within O(nq2) time, our algorithm generates a distribution statistically indistinguishable from discrete Gaussian at width s>ω(log n). Moreover, we apply our sampling algorithm to general high-dimensional dense lattices, and orthogonal lattices of matrices $matAinZ_q^{O(1) imes n}$. Compared with previous polynomial-time discrete Gaussian samplers, our algorithm does not rely on the short basis.