Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
复制标题
DOI：
10.1007/978-3-030-45374-9_21
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
N. Genise;Daniele Micciancio;Chris Peikert;Michael Walter
中科院分区：
文献类型：
--
作者：
N. Genise;Daniele Micciancio;Chris Peikert;Michael Walter
格上的离散高斯分布是基于格的密码学的核心，也是格的更广泛的计算和数学方面的核心。文献中包含了大量关于离散高斯在卷积和相关运算下的行为的有用定理。然而，尽管这些定理在结构上相似，但它们中的大多数在形式上是不可比较的，它们的证明往往是单一的，几乎是从头开始写的，这使得它们不必要地难以验证、理解和扩展。在这项工作中，我们提出了一个分析离散高斯分布上的线性运算的模块化框架。该框架抽象了高斯的细节，通常将证明简化为适当的线性变换和初等线性代数的选择。为了展示这种方法，我们建立了离散高斯的几个一般性质，并展示了如何获得所有先前的卷积定理(以及一些新的卷积定理)作为简单的推论。作为另一个应用，我们描述了一种带错误学习的自我约简(LWE)，它使用固定数量的样本来生成无限数量的额外样本(具有更大的误差)。作为独立的贡献，我们证明了次高斯型随机矩阵的奇异值集中界，并给出了通常用于生成格陷门的特定分布的更严密的启发式。这些界改进了陷门格密码系统的具体比特安全性估计。
Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.In this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.As a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems.