2018
A new discrete gaussian sampler over orthogonal lattices
Publication
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences , Volume E101.A - Issue 11 p. 1880- 1887
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 $\matA\in\Z_q^{O(1)\times n}$. Compared with previous polynomial-time discrete Gaussian samplers, our algorithm does not rely on the short basis.
Additional Metadata | |
---|---|
doi.org/10.1587/transfun.E101.A.1880 | |
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences | |
Cryptanalysis of Widely-used Hash Function Standards and Beyond | |
Organisation | Cryptology |
Xiao, D., Yu, Y., & Bi, J. (2018). A new discrete gaussian sampler over orthogonal lattices. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, E101.A(11), 1880–1887. doi:10.1587/transfun.E101.A.1880 |