抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法

doi:10.11896/jsjkx.210600017

计算机科学 ›› 2022, Vol. 49 ›› Issue (6A): 485-489.doi: 10.11896/jsjkx.210600017

抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法

梁懿雯, 杜育松

中山大学计算机学院广州 510006

出版日期:2022-06-10 发布日期:2022-06-08
通讯作者: 杜育松(duyusong@mail.sysu.edu.cn)
作者简介:(2190745539@qq.com)
基金资助:
广东省基础与应用基础研究重大项目(2019B030302008);国家自然科学基金(61972431);广东省基础与应用基础研究项目(2020A1515010687);广州市基础与应用基础研究项目(202102080332);中央高校基本科研业务费项目(青年教师培育)(19lgpy217);中山大学大学生创新创业训练计划项目(20211451)

Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao

LIANG Yi-wen, DU Yu-song

School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China

Online:2022-06-10 Published:2022-06-08
About author:LIANG Yi-wen,born in 2002,undergraduate.Her main research interests include cryptography and secrecy mana-gement.
DU Yu-song,born in 1982,Ph.D,asso-ciate professor.His main research inte-rests include cryptography and secrecy management.
Supported by:
Guangdong Major Project of Basic and Applied Research(2019B030302008),National Natural Science Foundation of China(61972431),Guangdong Basic and Applied Basic Research Foundation(2020A1515010687),Guangzhou Basic and Applied Basic Research Foundation(202102080332),Fundamental Research Funds for the Central Universities(19lgpy217) and Sun Yat-sen University Undergraduate Training Program for Innovation and Entrepreneurship(20211451).

摘要/Abstract

摘要： 格密码被认为是能够抵抗量子计算机攻击的新型密码。整数上的离散高斯采样算法在格密码中有着重要作用,但是容易遭受计时攻击。Knuth-Yao方法是一种基于二元概率矩阵的采样方法,对其进行简单改进可以实现常数运行时间,以抵御计时攻击,但极大地牺牲了采样速度。利用二元离散高斯分布的概率矩阵的移位性质,简化了Knuth-Yao方法的实现过程,减少了概率矩阵的存储空间。基于对Knuth-Yao方法中的概率矩阵的划分思想,有效地实现了抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法,并在较大程度上保证了采样速度。实验结果表明,与常规的基于Knuth-Yao的采样算法相比,改进的抵御计时攻击的采样算法采样速度仅降低了27.6%,较好地实现了采样速度与安全性的平衡。

关键词: Knuth-Yao方法, 二元高斯分布, 计时攻击, 离散高斯采样

Abstract: Lattice-based cryptography is considered to be a class of new type of cryptosystems that can resist the attacks from quantum computers.Discrete Gaussian sampling over the integers plays an important role in lattice-based cryptography,but it is vulnerable to timing attacks.The Knuth-Yao method is a sampling method based on the binary probability matrix.The simple improvement of Knuth-Yao can achieve constant running time to resist timing attacks,but it greatly sacrifices the sampling speed.By using the cyclic shift property of the probability matrix of the binary discrete Gaussian distribution,the Knuth-Yao is simplified,and the storage space of the probability matrix is reduced.Based on the idea of splitting the probability matrix,a class of timing attack resilient sampling algorithms for the binary discrete Gaussian based on Knuth-Yao is effectively implemented,and the sampling speed can be guaranteed to a large extent.Experimental results show that the sampling speed of the improved algorithm is only 27.6% lower than that of the conventional algorithm based on Knuth-Yao,which achieves a better balance between sampling speed and security.

Key words: Binary gaussian distribution, Discrete gaussian sampling, Knuth-Yao method, Timing attack

中图分类号:

TP309

梁懿雯, 杜育松. 抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法[J]. 计算机科学, 2022, 49(6A): 485-489. https://doi.org/10.11896/jsjkx.210600017

LIANG Yi-wen, DU Yu-song. Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao[J]. Computer Science, 2022, 49(6A): 485-489. https://doi.org/10.11896/jsjkx.210600017

参考文献

[1] PEIKERT C.A Decade of Lattice Cryptography[J].Founda-tions and Trendsin Theoretical Computer Science,2016,10(4):283-424.
[2] WANG X,LIU M.Survey of lattice-based cryptography[J].Journal of Cryptologic Research,2014,1(1):13-27.
[3] ZHANG P,JIANG H,CAI J,et al.Recent Advances in Lattice-Based Cryptography[J].Journal of Computer Research and Development,2017,54(10):2121-2129.
[4] PEIKERT C.An efficient and parallel gaussian sampler for lattices[C]//CRYPTO 2010.Springer,2010:80-97.
[5] GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trap-doors for hard lattices and newcryptographic constructions[C]//STOC 2008.ACM,2008:197-206.
[6] DUCAS L,DURMUS A,LEPOINT T,et al.Lattice signatures and bimodal gaussians[C]//CRYPTO 2013.Springer,2013:40-56.
[7] PREST T,FOUQUE P A,HOFFSTEIN J,et al.Falcon:Fast-Fourier Lattice-based Compact Signatures over NTRU[EB/OL].(2019-03)[2021-04-30].https://falcon-sign.info/.
[8] DWARAKANATH N C,GALBRAITH S D.Sampling fromdiscrete Gaussians for lattice-based cryptography on a constrained device[J].Applicable Algebra in Engineering,Communication and Computing,2014,25(3):159-180.
[9] FOLLÁTH J.Gaussian Sampling in Lattice Based Cryptography[J].Tatra Mountains Mathematical Publications,2015,60(1):1-23.
[10] 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]//CHES 2016.Springer,2016:323-345.
[11] ESPITAU T,FOUQUE P-A,GÉRARD B,et al.Sidechannel attacks on bliss lattice-based signatures:Exploiting branch tracing against strongswan and electromagnetic emanations in microcontrollers[C]//ACM SIGSAC 2017.ACM,2017:1857-1874.
[12] ROY S S,VERCAUTEREN F,VERBAUWHEDE I.High precision discrete gaussian sampling on fpgas[C]//SAC 2013.Springer,2013:383-401.
[13] BARTHE G,BELAÏD S,ESPITAU T,et al.GALACTICS:Gaussian Sampling for Lattice-Based Constant-Time Implementation of Cryptographic Signatures[C]//ACM SIGSAC CCS 2019.ACM,2019:2147-2164.
[14] 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.
[15] LU J,DU Y.Constant-time Implementation Method for Discrrte Gaussian Sampling on Integer[J].Computer Engineering,2020,46(8):119-123.
[16] MICCIANCIO D,WALTER M.Gaussian sampling over the integers:Efficient,generic,constant-time[C]//CRYPTO 2017.Springer,2017:455-485.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

抵御计时攻击的基于Knuth-Yao的二元离散高斯采样算法

Timing Attack Resilient Sampling Algorithms for Binary Gaussian Based on Knuth-Yao

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	陆垚, 陈开颜, 王寅龙, 尚倩伊. 针对AES查表法最后一轮加密的L3缓存攻击 L3 Cache Attack Against Last Round of Encryption AES Table Lookup Method 计算机科学, 2020, 47(6A): 375-380. https://doi.org/10.11896/JsJkx.190900157
[2]	周平,寇应展,王韬,赵新杰,刘会英. 一种改进的针对滑动窗口模幂运算实现的密码数据Cache计时攻击 Improved Data-Cache Timing Attack on Cryptography Adopting Sliding 计算机科学, 2013, 40(3): 201-205.
[3]	王寅龙,赵强,林克成,李志祥,王希武,邓高明. 面向计时攻击的形式化分析 Formal Approaches for Analyzing Timing Attacks 计算机科学, 2011, 38(10): 100-102.