一种抗侧信道攻击的SIS格签名实现方案
|
摘要
随着量子计算机的出现,传统的数字签名方案面临量子攻击,研究与设计能够抵抗量子计算机的数字签名算法是目前的研究热点.在密码算法的实际运行过程中,也时常面临侧信道攻击的风险.在设计安全高效的密码算法时,需要综合考虑多方面安全因素.格密码理论是后量子算法中的典型代表,基于格密码理论的数字签名算法能够在量子环境下安全运行,但在实际运行过程中,仍面临一阶能量攻击、计时攻击等侧信道攻击的威胁.为保证基于格密码理论的数字签名算法具备抵抗侧信道攻击的能力,本文提出一种能够抵抗侧信道攻击的SIS格签名实现方案.通过设置高斯取样参数,并对取样样本进行随机分割,扩大了取样范围,能够有效的抵抗Cache攻击;对签名过程中的私钥进行随机分割,实现对密钥的掩码操作,能够有效的抵抗一阶差分能量攻击.本文所提SIS签名实现方案所基于的困难问题是随机预言模型下可证明安全的,能够同时防御Cache攻击和一阶差分能量攻击,保证了密钥的安全性.
With the development of the quantum computer, the traditional digital signature schemes are challenged by the quantum attack, analysis and design of digital signature algorithms that can resist quantum computers are current research hotspots. In the actual execution of the cryptographic algorithms, it often faces the risk of side channel attacks. So, many factors need to be taken into consideration in designing a secure and effective cryptography algorithm. Lattice cryptography is a typical representative of post quantum algorithm, the digital signature algorithm based on lattice can posses security in the quantum environment, but it also face the thread of timing attack and first-order power attack and other side channel attacks in the real execution environment. In order to ensure the lattice cryptography having the ability to resist the side channel attacks, we propose an implementation scheme of SIS lattice signature against side channel attack. Through setting the parameters of Gauss sampling, and random segmentation of sampling samples, enlarging the range of sampling, it can have effective resistance against the Cache attack. We split the secret key in the signing process, this can obtain masking operation of the secret, and it can be effective in resisting the first-order differential power attack. The difficult problem which the SIS implementation scheme proposed in this paper is based on its provable security under the Random Oracle model, and this scheme can resist the Cache attack and first-order differential power attack, it can ensure the security of the key.
With the development of the quantum computer, the traditional digital signature schemes are challenged by the quantum attack, analysis and design of digital signature algorithms that can resist quantum computers are current research hotspots. In the actual execution of the cryptographic algorithms, it often faces the risk of side channel attacks. So, many factors need to be taken into consideration in designing a secure and effective cryptography algorithm. Lattice cryptography is a typical representative of post quantum algorithm, the digital signature algorithm based on lattice can posses security in the quantum environment, but it also face the thread of timing attack and first-order power attack and other side channel attacks in the real execution environment. In order to ensure the lattice cryptography having the ability to resist the side channel attacks, we propose an implementation scheme of SIS lattice signature against side channel attack. Through setting the parameters of Gauss sampling, and random segmentation of sampling samples, enlarging the range of sampling, it can have effective resistance against the Cache attack. We split the secret key in the signing process, this can obtain masking operation of the secret, and it can be effective in resisting the first-order differential power attack. The difficult problem which the SIS implementation scheme proposed in this paper is based on its provable security under the Random Oracle model, and this scheme can resist the Cache attack and first-order differential power attack, it can ensure the security of the key.
引文
[1]DIFFIE W,HELLMAN M.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.[DOI:10.1109/TIT.1976.1055638]
[2]AJTAI M.Generating hard instances of lattice problems[C].In:Twenty-eighth ACM Symposium on Theory of Computing.ACM,1996:99-108.[DOI:10.1145/237814.237838]
[3]GOLDREICH O,GOLDWASSER S,HALEVI S.Public-key cryptosystems from lattice reduction problems[C].In:Advances in Cryptology—CRYPTO 1997.Springer Berlin Heidelberg,1997:112-131.[DOI:10.1007/BFb0052231]
[4]HOFFSTEIN J,HOWGRAVE-GRAHAM N,PIPHER J,et al.NTRUSIGN:Digital signatures using the NTRU lattice[C].In:Cryptographers'Track at the RSA Conference.Springer Berlin Heidelberg,2003:122-140.[DOI:10.1007/3-540-36563-X_9]
[5]LYUBASHEVSKY V,MICCIANCIO D.Asymptotically efficient lattice-based digital signatures[J].Journal of Cryptology,2008,4948(6):1-24.[DOI:10.1007/s00145-017-9270-z]
[6]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C].In:Proceedings of the 40th Annual ACM Symposium on Theory of Computing.ACM,2008:197-206.[DOI:10.1145/1374376.1374407]
[7]CASH D,HOFHEINZ D,KILTZ E,et al.Bonsai trees,or how to delegate a lattice basis[C].In:Advances in Cryptology—EUROCRYPT 2010.Springer Berlin Heidelberg,2010:523-552.[DOI:10.1007/978-3-642-13190-5_27]
[8]WANG F H,HU Y P,WANG C X.A lattice-based ring signature scheme from bonsai trees[J].Journal of Electronics&Information Technology,2010,32(10):2400-2403.[DOI:10.3724/SP.J.1146.2009.01491]王凤和,胡予濮,王春晓.格上基于盆景树模型的环签名[J].电子与信息学报,2010,32(10):2400-2403.[DOI:10.3724/SP.J.1146.2009.01491]
[9]BRUINDERINK L G,H(U|¨)LSING A,LANGE T,et al.Flush,Gauss,and reload—A cache attack on the BLISS lattice-based signature scheme[C].In:Cryptographic Hardware and Embedded Systems—CHES 2016.Springer Berlin Heidelberg,2016:323-345.[DOI:10.1007/978-3-662-53140-2_16]
[10]REPARAZ O,ROY S S,CLERCQ R D.Masking ring-LWE[J].Journal of Cryptographic Engineering,2016,6(2):139-153.[DOI:10.1007/s13389-016-0126-5]
[11]BINDEL N,BUCHMANN J,KRAMER J.Lattice-based signature schemes and their sensitivity to fault attacks[C].In:The Workshop on Fault Diagnosis&Tolerance in Cryptography.IEEE Computer Society,2016:63-77.[DOI:10.1109/FDTC.2016.11]
[12]C AO J,YANG Y T,LI Z C.Lattice signature and its application based on small integer solution problem[J].Journal of Computer Applications,2014,34(1):78-81.[DOI:10.11772/j.issn.1001-9081.2014.01.0078]曹杰,杨亚涛,李子臣.基于小整数解问题上的格签名方案及其应用[J].计算机应用,2014,34(1):78-81.[DOI:10.11772/j.issn.1001-9081.2014.01.0078]
[13]MICCIANCIO D,REGEV O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM Journal on Computer,2007,37(1):267-302.[DOI:10.1109/FOCS.2004.72]
[14]LYUBASHEVSKY V.Lattice signatures without trapdoors[C].In:Advances in Cryptology—EUROCRYPT 2012.Springer Berlin Heidelberg,2012:738-755.[DOI:10.1007/978-3-642-29011-4_43]
[2]AJTAI M.Generating hard instances of lattice problems[C].In:Twenty-eighth ACM Symposium on Theory of Computing.ACM,1996:99-108.[DOI:10.1145/237814.237838]
[3]GOLDREICH O,GOLDWASSER S,HALEVI S.Public-key cryptosystems from lattice reduction problems[C].In:Advances in Cryptology—CRYPTO 1997.Springer Berlin Heidelberg,1997:112-131.[DOI:10.1007/BFb0052231]
[4]HOFFSTEIN J,HOWGRAVE-GRAHAM N,PIPHER J,et al.NTRUSIGN:Digital signatures using the NTRU lattice[C].In:Cryptographers'Track at the RSA Conference.Springer Berlin Heidelberg,2003:122-140.[DOI:10.1007/3-540-36563-X_9]
[5]LYUBASHEVSKY V,MICCIANCIO D.Asymptotically efficient lattice-based digital signatures[J].Journal of Cryptology,2008,4948(6):1-24.[DOI:10.1007/s00145-017-9270-z]
[6]GENTRY C,PEIKERT C,VAIKUNTANATHAN V.Trapdoors for hard lattices and new cryptographic constructions[C].In:Proceedings of the 40th Annual ACM Symposium on Theory of Computing.ACM,2008:197-206.[DOI:10.1145/1374376.1374407]
[7]CASH D,HOFHEINZ D,KILTZ E,et al.Bonsai trees,or how to delegate a lattice basis[C].In:Advances in Cryptology—EUROCRYPT 2010.Springer Berlin Heidelberg,2010:523-552.[DOI:10.1007/978-3-642-13190-5_27]
[8]WANG F H,HU Y P,WANG C X.A lattice-based ring signature scheme from bonsai trees[J].Journal of Electronics&Information Technology,2010,32(10):2400-2403.[DOI:10.3724/SP.J.1146.2009.01491]王凤和,胡予濮,王春晓.格上基于盆景树模型的环签名[J].电子与信息学报,2010,32(10):2400-2403.[DOI:10.3724/SP.J.1146.2009.01491]
[9]BRUINDERINK L G,H(U|¨)LSING A,LANGE T,et al.Flush,Gauss,and reload—A cache attack on the BLISS lattice-based signature scheme[C].In:Cryptographic Hardware and Embedded Systems—CHES 2016.Springer Berlin Heidelberg,2016:323-345.[DOI:10.1007/978-3-662-53140-2_16]
[10]REPARAZ O,ROY S S,CLERCQ R D.Masking ring-LWE[J].Journal of Cryptographic Engineering,2016,6(2):139-153.[DOI:10.1007/s13389-016-0126-5]
[11]BINDEL N,BUCHMANN J,KRAMER J.Lattice-based signature schemes and their sensitivity to fault attacks[C].In:The Workshop on Fault Diagnosis&Tolerance in Cryptography.IEEE Computer Society,2016:63-77.[DOI:10.1109/FDTC.2016.11]
[12]C AO J,YANG Y T,LI Z C.Lattice signature and its application based on small integer solution problem[J].Journal of Computer Applications,2014,34(1):78-81.[DOI:10.11772/j.issn.1001-9081.2014.01.0078]曹杰,杨亚涛,李子臣.基于小整数解问题上的格签名方案及其应用[J].计算机应用,2014,34(1):78-81.[DOI:10.11772/j.issn.1001-9081.2014.01.0078]
[13]MICCIANCIO D,REGEV O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM Journal on Computer,2007,37(1):267-302.[DOI:10.1109/FOCS.2004.72]
[14]LYUBASHEVSKY V.Lattice signatures without trapdoors[C].In:Advances in Cryptology—EUROCRYPT 2012.Springer Berlin Heidelberg,2012:738-755.[DOI:10.1007/978-3-642-29011-4_43]