IEICE TRANSACTIONS on Fundamentals
A New Discrete Gaussian Sampler over Orthogonal Lattices
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.11 pp.1880-1887
- Publication Date
- 2018/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.1880
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Dianyan XIAO
Tsinghua University
Yang YU
Tsinghua University
Jingguo BI
Tsinghua University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
