Merge-Exchange Sort Based Discrete Gaussian Sampler with Fixed Memory Access Pattern
Merge-Exchange Sort Based Discrete Gaussian Sampler with Fixed Memory Access Pattern
复制标题
DOI：
10.1109/icfpt47387.2019.00023
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Shanquan Tian;Wen Wang;Jakub Szefer
中科院分区：
文献类型：
--
作者：
Shanquan Tian;Wen Wang;Jakub Szefer
离散高斯采样器用于从离散高斯分布中采样整数。由于此功能用于基于格的方案的密钥生成、签名或密钥封装等操作，因此它是这些密码算法的基本构建块。现代离散高斯采样器在密码算法中使用时，一个必需的特征是恒定时间，以确保针对定时侧信道攻击的安全性。此外，通常希望通过限制攻击者可以从测量电源跟踪中获得的信息量来最小化电源或EM侧通道攻击的可能性。为了解决硬件上对具有这些特性的高斯采样器的需求，提出了一种在现场可编程门阵列上实现的固定时间离散高斯采样器的硬件实现方案。该设计采用基于累积分布表(CDT)的方法。此外，新的采样器使用合并交换排序算法，该算法能够批量生成样本。在硬件中，由于使用了合并交换排序算法，无论秘密样本的值是多少，存储器访问模式始终是固定的。这增加了采样器对潜在功率或EM侧通道攻击的抵抗力，因为存储器使用和访问与秘密值无关。提出的采样器可以在编译时使用以下高斯参数进行完全参数化：标准偏差、精度和截尾，从而生成与密码算法所需的参数完全匹配的硬件设计。此外，它可以在编译时使用一次生成的样本数的批处理大小进行参数化。设计评估是基于各种Xilinx现场可编程门阵列的综合数据。
Discrete Gaussian samplers are used to sample integers from a discrete Gaussian distribution. Since this functionality is used in operations such as key generation, signing, or key encapsulation of lattice-based schemes, it is a fundamental building block of these cryptographic algorithms. One required feature of modern discrete Gaussian samplers when used in cryptographic algorithms is to be constant-time, to ensure security against timing side-channel attacks. Further, it is often desired to minimize potential for power or EM side-channel attacks by limiting how much information an attacker can gain from measuring power traces. To address the need for having a Gaussian sampler with these features in hardware, this paper presents a novel hardware implementation of a constant-time discrete Gaussian sampler with fixed memory access pattern realized on FPGAs. The design uses an approach based on Cumulative Distribution Table (CDT). Further, the new sampler uses a merge-exchange sort algorithm that enables generating the samples in batches. In the hardware, due to the use of the merge-exchange sort algorithm, the memory access pattern is always fixed, regardless of the values of the secret samples. This increases the resistance of the sampler to potential power or EM side-channel attacks as memory usage and accesses are independent of the secret values. The presented sampler can be fully parameterized at compile-time with the following Gaussian parameters: standard deviation, precision, and tail cut, generating a hardware design that matches the exact parameters required by the cryptographic algorithm. In addition, it can be parameterized, at compile-time, with the batch size for the number of samples to generate at a time. The design evaluation is based on synthesis data for various Xilinx FPGAs.