The search functionality is under construction.
The search functionality is under construction.

A New Discrete Gaussian Sampler over Orthogonal Lattices

Dianyan XIAO, Yang YU, Jingguo BI

  • Full Text Views

    0

  • Cite this

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