FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers
FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers
复制标题
DOI：
10.1109/tc.2019.2940949
复制
发表时间：
2020-01
影响因子：
3.7
通讯作者：
Raymond K. Zhao;Ron Steinfeld;A. Sakzad
中科院分区：
文献类型：
--
作者：
Raymond K. Zhao;Ron Steinfeld;A. Sakzad
离散高斯采样器是实现格密码系统的基本工具之一。然而，朴素的离散高斯采样实现遭受边信道漏洞，现有的对策通常会在运行速度或内存消耗方面引入显着的开销。在本文中，我们提出了一个快速，紧凑，恒定时间的二进制采样算法，最初介绍了布利斯签名方案的实现。我们的实现采用了Rényi散度和超越函数多项式逼近技术。我们的计划的效率是独立的标准偏差，我们证明，我们的实现速度更快或更紧凑，比现有的几个恒定时间采样器。此外，我们展示了我们的实现技术的性能，并与两个现有的签名方案：qTesla和猎鹰。另一方面，卷积定理通常通过组合具有小得多的标准偏差的样本来适应从较大的标准偏差中采样。作为一个额外的贡献，我们显示更好的参数的卷积定理。
The discrete Gaussian sampler is one of the fundamental tools in implementing lattice-based cryptosystems. However, a naive discrete Gaussian sampling implementation suffers from side-channel vulnerabilities, and the existing countermeasures usually introduce significant overhead in either the running speed or the memory consumption. In this paper, we propose a fast, compact, and constant-time implementation of the binary sampling algorithm, originally introduced in the BLISS signature scheme. Our implementation adapts the Rényi divergence and the transcendental function polynomial approximation techniques. The efficiency of our scheme is independent of the standard deviation, and we show evidence that our implementations are either faster or more compact than several existing constant-time samplers. In addition, we show the performance of our implementation techniques applied to and integrated with two existing signature schemes: qTesla and Falcon. On the other hand, the convolution theorems are typically adapted to sample from larger standard deviations, by combining samples with much smaller standard deviations. As an additional contribution, we show better parameters for the convolution theorems.