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.
Dianyan XIAO
Tsinghua University
Yang YU
Tsinghua University
Jingguo BI
Tsinghua University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Dianyan XIAO, Yang YU, Jingguo BI, "A New Discrete Gaussian Sampler over Orthogonal Lattices" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 11, pp. 1880-1887, November 2018, doi: 10.1587/transfun.E101.A.1880.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1880/_p
Copy
@ARTICLE{e101-a_11_1880,
author={Dianyan XIAO, Yang YU, Jingguo BI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Discrete Gaussian Sampler over Orthogonal Lattices},
year={2018},
volume={E101-A},
number={11},
pages={1880-1887},
abstract={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.},
keywords={},
doi={10.1587/transfun.E101.A.1880},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - A New Discrete Gaussian Sampler over Orthogonal Lattices
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1880
EP - 1887
AU - Dianyan XIAO
AU - Yang YU
AU - Jingguo BI
PY - 2018
DO - 10.1587/transfun.E101.A.1880
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2018
AB - 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.
ER -