一种抵御计时攻击的指数Bernoulli精确采样算法

An Algorithm for Sampling Exactly from Exponential Bernoulli Distributions with Resistance against Timing Attacks

整数上的离散高斯采样是格密码的基础构建之一。拒绝采样是实现整数上离散高斯采样的一种主要的方法,而使用拒绝采样的关键是实现一个以指数函数为参数的Bernoulli分布的采样过程。这一采样过程也是决定整个采样算法能否抵御计时攻击的关键。对于实数x>0,借鉴SUN等人提出的一种针对指数函数Bernoulli分布β_(2)-x的等时采样算法,文章给出了一种可供选择的针对Bernoulli分布β_(2)-x的抵御计时攻击的精确采样算法,该算法能防止x的取值因计时攻击而遭到泄露,并且不需要(在线的)浮点运算,同时还能避免SUN等人的采样算法在实际实现中产生的统计误差,从而确保采样结果的精确性。实验结果验证了这一精确采样算法的有效性。

Discrete Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography.Rejection sampling is one of the main methods for the discrete Gaussian sampling over the integers.The key of using rejection sampling is to implement a sampling procedure for Bernoulli distributions with exponential functions as parameters,and this sampling procedure is also the key to determine whether the whole sampling algorithm can resist timing attacks.For a real x>0,based on the isochronous sampling algorithm given by SUN et al.for the“exponential Bernoulli distribution”β_(2)-x,an alternative exact sampling algorithm with timing attack resistance is proposed for β_(2)-x.It can prevent the leakage of the information on the value of x caused by timing attacks,and does not require(online)floating-point arithmetic,and can also avoid the statistical error in the practical implementation of the sampling algorithm of SUN et al.,so as to ensure the exactness of sampling results in practice.Experimental results demonstrate the effectiveness of this exact sampling algorithm.