Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 485-489.doi: 10.11896/jsjkx.210600017

• Information Security • Previous Articles     Next Articles

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

LIANG Yi-wen, DU Yu-song   

  1. 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).

PDF (PC)

725

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

CLC Number: 

  • TP309
[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.
[1] LU Yao, CHEN Kai-yan, WANG Yin-long and SHANG Qian-yi. L3 Cache Attack Against Last Round of Encryption AES Table Lookup Method [J]. Computer Science, 2020, 47(6A): 375-380.
[2] . Improved Data-Cache Timing Attack on Cryptography Adopting Sliding [J]. Computer Science, 2013, 40(3): 201-205.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.