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

doi:10.3969/j.issn.1671-1122.2024.06.004

信息网络安全 ›› 2024, Vol. 24 ›› Issue (6): 855-862.doi: 10.3969/j.issn.1671-1122.2024.06.004

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

杜育松¹(), 江思维¹, 沈静², 张家豪¹

1.中山大学计算机学院，广州 510006
2.广东工贸职业技术学院，广州 510510

收稿日期:2024-04-06 出版日期:2024-06-10 发布日期:2024-07-05
通讯作者: 杜育松 duyusong@mail.sysu.edu.cn
作者简介:杜育松（1982—），男，河北，副教授，博士，主要研究方向为密码学|江思维（2000—），男，辽宁，硕士研究生，主要研究方向为密码学|沈静（1980—），女，浙江，讲师，硕士，主要研究方向为网络与信息安全|张家豪（2001—），男，广东，主要研究方向为保密管理
基金资助:
广东省基础与应用基础研究重大项目(2019B030302008);广东省基础与应用基础研究项目(2022A1515011512);广东工贸职业技术学院校级科研项目(2021-ZK-17)

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

DU Yusong¹(), JIANG Siwei¹, SHEN Jing², ZHANG Jiahao¹

1. School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China
2. Guangdong Polytechnic of Industry and Commerce, Guangzhou 510510, China

Received:2024-04-06 Online:2024-06-10 Published:2024-07-05

摘要/Abstract

摘要：

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

关键词: 格密码, 离散高斯采样, Bernoulli分布, 计时攻击

Abstract:

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.

Key words: lattice-based cryptography, discrete Gaussian sampling, Bernoulli distribution, timing attack

中图分类号:

TP309

杜育松, 江思维, 沈静, 张家豪. 一种抵御计时攻击的指数Bernoulli精确采样算法[J]. 信息网络安全, 2024, 24(6): 855-862.

DU Yusong, JIANG Siwei, SHEN Jing, ZHANG Jiahao. An Algorithm for Sampling Exactly from Exponential Bernoulli Distributions with Resistance against Timing Attacks[J]. Netinfo Security, 2024, 24(6): 855-862.

图/表 2

参考文献 24

[1]	WANG Xiaoyun, LIU Mingjie. Survey of Lattice-Based Cryptography[J]. Journal of Cryptologic Research, 2014, 1(1): 13-27.
	王小云, 刘明洁. 格密码学研究[J]. 密码学报, 2014, 1(1): 13-27. doi: 10.13868/j.cnki.jcr.000002
[2]	PEIKERT C. A Decade of Lattice Cryptography[J]. Foundations and Trends in Theoretical Computer Science, 2016, 10(4): 283-424.
[3]	ESPITAU T, WALLET A, YU Y. On Gaussian Sampling, Smoothing Parameter and Application to Signatures[C]// IACR. The 29th International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2023: 65-97.
[4]	PEIKERT C. An Efficient and Parallel Gaussian Sampler for Lattices[C]// IACR. 30th Annual Cryptology Conference. Heidelberg: Springer, 2010: 80-97.
[5]	DEVEVEY J, PASSELÈGUE A, STEHLÉ D. G+G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians[C]// IACR. The 29th International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2023: 37-64.
[6]	MICCIANCIO D, PEIKERT C. Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller[C]// IACR. 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2012: 700-718.
[7]	GENISE N, MICCIANCIO D. Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus[C]// IACR. 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2018: 174-203.
[8]	CANONNE C L, KAMATH G, STEINKE T. The Discrete Gaussian for Differential Privacy[C]// Curran Associates. 33rd Annual Conference on Neural Information Processing Systems. New York: Curran Associates, 2020: 15676-15688.
[9]	DWARAKANATH N C, GALBRAITH S D. Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device[J]. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 159-180.
[10]	FOLLÁTH J. Gaussian Sampling in Lattice Based Cryptography[J]. Tatra Mountains Mathematical Publications, 2014, 60(1): 1-23.
[11]	BRUINDERINK L G, HÜLSING A, LANGE T, et al. Flush, Gauss, and Reload-A Cache Attack on the BLISS Lattice-Based Signature Scheme[C]// IACR. 18th International Conference on Cryptographic Hardware and Embedded Systems. Heidelberg: Springer, 2016: 323-345.
[12]	ESPITAU T, FOUQUE P-A, GÉRARD B, et al. Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against StrongSwan and Electromagnetic Emanations in Microcontrollers[C]// ACM. 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1857-1874.
[13]	HOWE J, PREST T, RICOSSET T, et al. Isochronous Gaussian Sampling: From Inception to Implementation[C]// IACR. 11th International Conference on Post-Quantum Cryptography. Heidelberg: Springer, 2020: 53-71.
[14]	SUN Shuo, ZHOU Yongbin, JI Yunfeng, et al. Generic, Efficient and Isochronous Gaussian Sampling over the Integers[J]. Cybersecurity, 2022, 5: 10-22.
[15]	KARMAKAR A, ROY S S, REPARAZ O, et al. Constant-Time Discrete Gaussian Sampling[J]. IEEE Transactions on Computers, 2018, 67(11): 1561-1571.
[16]	ZHAO R K, STEINFELD R, SAKZAD A. FACCT: Fast, Compact, and Constant-Time Discrete Gaussian Sampler over Integers[J]. IEEE Transactions on Computers, 2020, 69(1): 126-137.
[17]	DU Yusong, FAN Baoying, WEI Baodian. A Constant-Time Sampling Algorithm for Binary Gaussian Distribution over the Integers[J]. Information Processing Letters, 2022, 176: 62-76.
[18]	DUCAS L, DURMUS A, LEPOINT T, et al. Lattice Signatures and Bimodal Gaussians[C]// IACR. 33rd Annual Cryptology Conference. Heidelberg: Springer, 2013: 40-56.
[19]	KARNEY C F. Sampling Exactly from the Normal Distribution[J]. ACM Transactions on Mathematical Software, 2016, 42(1): 1-14.
[20]	WANG Jiabo, LING Cong. Polar Sampler: A Novel Bernoulli Sampler Using Polar Codes with Application to Integer Gaussian Sampling[J]. Designs, Codes and Cryptography, 2023, 91(5): 1779-1811.
[21]	BARTHE G, BELAÏD S, ESPITAU T, et al. GALACTICS: Gaussian Sampling for Lattice-Based Constant- Time Implementation of Cryptographic Signatures, Revisited[C]// ACM. The 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 2147-2164.
[22]	BAI S, LEPOINT T, ROUX-LANGLOIS A, et al. Improved Security Proofs in Lattice-Based Cryptography: Using the Renyi Divergence Rather than the Statistical Distance[J]. Journal of Cryptology, 2018, 31(2): 610-640.
[23]	PREST T. Sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence[C]// Springer. The 23rd International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2017: 347-374.
[24]	MICCIANCIO D, WALTER M. Gaussian Sampling over the Integers:Efficient, Generic, Constant-Time[C]// IACR. 37th Annual Cryptology Conference. Heidelberg: Springer, 2017: 455-485.

参数x	算法2/ms	算法4/ms
1/5	172	347
2/5	175	367
1/2	157	363
3/5	173	332
4/5	174	346

参数k	算法2/s	算法4/s
215	8.423×10⁶	7.140×10⁶
107	8.008×10⁶	7.201×10⁶
250	7.301×10⁶	6.430×10⁶
271	7.283×10⁶	6.426×10⁶

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 24

相关文章 7

编辑推荐

Metrics

本文评价

[1]	叶清, 何俊霏, 杨智超. 基于格的可搜索公钥加密研究进展[J]. 信息网络安全, 2024, 24(6): 903-916.
[2]	刘芹, 王卓冰, 余纯武, 王张宜. 面向云安全的基于格的高效属性基加密方案[J]. 信息网络安全, 2023, 23(9): 25-36.
[3]	俞惠芳, 乔一凡, 孟茹. 面向区块链金融的抗量子属性基门限环签密方案[J]. 信息网络安全, 2023, 23(7): 44-52.
[4]	陶云亭, 孔凡玉, 于佳, 徐秋亮. 抗量子格密码体制的快速数论变换算法研究综述[J]. 信息网络安全, 2021, 21(9): 46-51.
[5]	李鱼, 韩益亮, 李喆, 朱率率. 基于LWE的抗量子认证密钥交换协议[J]. 信息网络安全, 2020, 20(10): 92-99.
[6]	江明明, 赵利军, 王艳, 王保仓. 面向云数据共享的量子安全的无证书双向代理重加密[J]. 信息网络安全, 2018, 18(8): 17-24.
[7]	陈莉, 顾纯祥, 尚明君. 抗量子攻击的高效盲签名方案[J]. 信息网络安全, 2017, 17(10): 36-41.