基于格的前向安全签名方案
|
摘要
作为应对量子时代密码危机的有效措施,抗量子计算攻击的公钥密码体制得到了国内外学者的广泛关注.基于格的公钥密码体制除抗量子计算攻击外,还有其他优良特性,如最差情况/平均情况等价性以及运算高效性等,因此基于格的公钥密码体制成为抗量子计算密码领域的一个研究热点.签名私钥泄露是签名体制面临的最严重的安全威胁.前向安全签名体制能有效减轻签名私钥泄露所带来的危害,因此它是一种极具应用价值的带附加性质的签名体制.有鉴于此,本文首先基于格技术构造了一个前向安全签名方案,该方案的签名过程由Gentry等提出的带前像抽样的陷门单向函数实现,密钥更新过程由Cash等提出的被称为盆景树的密码结构实现.且我们所提出的方案使用了二叉树结构.然后,在随机预言模型下基于小整数解(SIS)问题困难性证明了所提出的方案的前向安全性,即在适应性选择消息攻击下的存在性不可伪造性.最后,以所提出的方案为基础,本文构造了一个基于格的前向安全的身份基签名方案.
As an effective measure to cope with cryptography crisis in the quantum age, public-key cryptography against quantum computation attacks have drawn extensive attention and research internationally. Besides the security against quantum computation attacks, lattice based public-key cryptography has other attractive features, such as worse-case/average-case equivalence, high computational efficiency. So how to thwart quantum computation attacks has become a hot research topic in public-key cryptography. Exposure of the secret signing key is the greatest threat against the security of a digital signature scheme. Forward-secure signature scheme can effectively mitigate the damage caused by exposure of the secret signing key, hence, a forward-secure signature scheme is a digital signature scheme with additional properties and has great significance in applications. Given the above, this paper proposes a forward-secure signature scheme by using lattice techniques.In the proposed scheme, the signing procedure takes the advantage of a trapdoor one-way function with preimage sampling proposed by Gentry et al, and the secret key update procedure makes use of the cryptographic structure called the bonsai tree proposed by Cash et al. Furthermore, the proposed scheme employs the binary tree structure, and the paper proves that the proposed scheme satisfies the forward security, existential unforgeability against adaptively chosen message attacks, under the random oracle model based on the intractability of the small integer solution(SIS) problem. Finally, based on the proposed scheme, this paper constructs a lattice based forward-secure identity-based signature scheme.
As an effective measure to cope with cryptography crisis in the quantum age, public-key cryptography against quantum computation attacks have drawn extensive attention and research internationally. Besides the security against quantum computation attacks, lattice based public-key cryptography has other attractive features, such as worse-case/average-case equivalence, high computational efficiency. So how to thwart quantum computation attacks has become a hot research topic in public-key cryptography. Exposure of the secret signing key is the greatest threat against the security of a digital signature scheme. Forward-secure signature scheme can effectively mitigate the damage caused by exposure of the secret signing key, hence, a forward-secure signature scheme is a digital signature scheme with additional properties and has great significance in applications. Given the above, this paper proposes a forward-secure signature scheme by using lattice techniques.In the proposed scheme, the signing procedure takes the advantage of a trapdoor one-way function with preimage sampling proposed by Gentry et al, and the secret key update procedure makes use of the cryptographic structure called the bonsai tree proposed by Cash et al. Furthermore, the proposed scheme employs the binary tree structure, and the paper proves that the proposed scheme satisfies the forward security, existential unforgeability against adaptively chosen message attacks, under the random oracle model based on the intractability of the small integer solution(SIS) problem. Finally, based on the proposed scheme, this paper constructs a lattice based forward-secure identity-based signature scheme.
引文
[1]AJTAI M.Generating hard instances of lattice problems[C].In:Proceedings of the 28th Annual ACM Symposium on Theory of Computing—STOC 1996.ACM,1996:99–108.
[2]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—STOC 2008.ACM,2008:197–206.
[3]BELLARE M,ROGAWAY P.Random oracles are practical:A paradigm for designing efficient protocols[C].In:Proceedings of the 1st ACM Conference on Computer and Communications Security—CCS 1993.ACM,1993:62–73.
[4]CASH D,HOFHEINZ D,KILTZ E,et al.Bonsai tree,or how to delegate a lattice basis[J].Journal of Cryptology.2012,25(4):601–639.
[5]RUCKERT M.Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[C].In:Proceedings of the 3rd International Workshop on Post-quantum Cryptography—PQCrypto 2010.Springer Berlin Heidelberg,2010:182–200.
[6]PEIKERT C.A decade of lattice cryptography[R].Cryptology e Print Archive,Report 2015/939,2015.
[7]ANDERSON R.Two remarks on public key cryptology[EB/OL].http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-549.pdf.2002.
[8]BELLARE M,MINER S K.A forward-secure digital signature scheme[C].In:Advances in Cryptology—Crypto 1999.Springer Berlin Heidelberg,1999:431–448.
[9]KANG B G,PARK J H,HAHN S G.A New Forward Secure Signature Scheme[J].IACR Cryptology e Print Archive,2004,2004:183.
[10]CANETTI R,HALEVI S,KATZ J.A forward-secure public-key encryption scheme[J].Journal of cryptology.2007,20(3):265–294.
[11]YU J,HAO R,KONG F,et al.Forward-secure identity-based signature:security notions and construction[J].Information sciences.2011,181(3):648–660.
[12]ZHANG X,XU C,JIN C,et al.Efficient forward secure identity-based shorter signature from lattice[J].Computers and electrical engineering.2014,40(6):1963–1971.
[13]XIANG X Y.Identity-based forward secure signature scheme from lattice[J].Computer Engineering,2015,41(9):155–158.向新银.格上基于身份的前向安全签名方案[J].计算机工程,2015,41(9):155–158.
[14]MICCIANCIO D,REGEV O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM journal on computing.2007,37(1):267–302.
[15]ALWEN J,PEIKERT C.Generating shorter bases for hard random lattices[J].Theory of Computing Systems.2011,48(3):535–553.
[16]GOLDWASSER S,MICALI S,RIVEST R L.A digital signature scheme secure against adaptive chosen-message attacks[J].SIAM journal on computing.1988,17(2):281–308.
[17]PATERSON K G,SCHULDT J C N.Efficient identity-based signatures secure in the standard model[C].In:Proceedings of the 11th Australasian Conference on Information Security and Privacy—ACISP 2006.Springer Berlin Heidelberg,2006:207–222.
[18]BONEH D,BOYEN X.Efficient selective-ID secure identity-based encryption without random oracles[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:223–238.
[2]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—STOC 2008.ACM,2008:197–206.
[3]BELLARE M,ROGAWAY P.Random oracles are practical:A paradigm for designing efficient protocols[C].In:Proceedings of the 1st ACM Conference on Computer and Communications Security—CCS 1993.ACM,1993:62–73.
[4]CASH D,HOFHEINZ D,KILTZ E,et al.Bonsai tree,or how to delegate a lattice basis[J].Journal of Cryptology.2012,25(4):601–639.
[5]RUCKERT M.Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles[C].In:Proceedings of the 3rd International Workshop on Post-quantum Cryptography—PQCrypto 2010.Springer Berlin Heidelberg,2010:182–200.
[6]PEIKERT C.A decade of lattice cryptography[R].Cryptology e Print Archive,Report 2015/939,2015.
[7]ANDERSON R.Two remarks on public key cryptology[EB/OL].http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-549.pdf.2002.
[8]BELLARE M,MINER S K.A forward-secure digital signature scheme[C].In:Advances in Cryptology—Crypto 1999.Springer Berlin Heidelberg,1999:431–448.
[9]KANG B G,PARK J H,HAHN S G.A New Forward Secure Signature Scheme[J].IACR Cryptology e Print Archive,2004,2004:183.
[10]CANETTI R,HALEVI S,KATZ J.A forward-secure public-key encryption scheme[J].Journal of cryptology.2007,20(3):265–294.
[11]YU J,HAO R,KONG F,et al.Forward-secure identity-based signature:security notions and construction[J].Information sciences.2011,181(3):648–660.
[12]ZHANG X,XU C,JIN C,et al.Efficient forward secure identity-based shorter signature from lattice[J].Computers and electrical engineering.2014,40(6):1963–1971.
[13]XIANG X Y.Identity-based forward secure signature scheme from lattice[J].Computer Engineering,2015,41(9):155–158.向新银.格上基于身份的前向安全签名方案[J].计算机工程,2015,41(9):155–158.
[14]MICCIANCIO D,REGEV O.Worst-case to average-case reductions based on Gaussian measures[J].SIAM journal on computing.2007,37(1):267–302.
[15]ALWEN J,PEIKERT C.Generating shorter bases for hard random lattices[J].Theory of Computing Systems.2011,48(3):535–553.
[16]GOLDWASSER S,MICALI S,RIVEST R L.A digital signature scheme secure against adaptive chosen-message attacks[J].SIAM journal on computing.1988,17(2):281–308.
[17]PATERSON K G,SCHULDT J C N.Efficient identity-based signatures secure in the standard model[C].In:Proceedings of the 11th Australasian Conference on Information Security and Privacy—ACISP 2006.Springer Berlin Heidelberg,2006:207–222.
[18]BONEH D,BOYEN X.Efficient selective-ID secure identity-based encryption without random oracles[C].In:Advances in Cryptology—EUROCRYPT 2004.Springer Berlin Heidelberg,2004:223–238.