标准模型下可证安全的基于身份的高效签名方案
资料包括： 论文(9页6315字)
说明：
摘 要：基于身份的公钥密码体制克服了传统公钥密码体制所带来的公钥证书存储和管理开销问题；目前大多数基于身份的数字签名方案的安全性是基于随机预言模型进行证明，但随机预言机的实现方式可能会导致方案的不安全，如哈希函数，往往返回的结果并不是随机的。本文提出一种安全、高效的基于身份的签名方案，并且在标准模型下证明该方案对自适应选择消息攻击是存在不可伪造的，方案的安全性可规约为CDH困难假定。与现有的标准模型下安全的基于身份的签名方案相比，方案的通信代价更小，执行效率更高。
关键词: 基于身份的签名；双线性对；标准模型；CDH-问题；选择消息攻击
Abstract: Compared with the traditional public key cryptosystem, identity-based cryptosystem can simplify the key management procedure from the view point of the efficiency and convenience. Most of identity-based signature schemes are secure in the random oracle model, but for which any implementation of the random oracle results in insecure schemes. For example, when random oracle is instantiated with concrete hash functions, the resulting scheme is nonrandom which may not be secure. In this paper, we propose an efficient and provably secure identity-based signature scheme. Our scheme is existentially unforgeable against adaptive chosen message attacks under the computational Diffie-Hellman assumption in the standard model. Compared with the known identity-based scheme secure in the standard model, our scheme enjoys shorter signature length and less operation.
Key words: identity-based signature; bilinear pairings; standard model; CDH-problem; chosen message attack
1 引言
1984年，Shamir提出基于身份的公钥密码体制，在这种体制中，Shamir建议使用能标识用户身份的信息为公钥，比如名字、IP地址或者Email地址。基于身份密码体制的主要优势在于它减轻了用户对公钥证书的需要和依赖。2001年，Boneh和Franklin利用Weil配对技术(Weil pairing)提出了第一个安全、实用的基于身份的加密方案，自从那之后，基于身份的密码体制引起了国内外众多学者的广泛关注并得到迅速发展，提出了大量的基于身份的加密和签名方案[3,4,5,6,7,8,9,10]，这些方案都是在随机预言模型(Random Oracle Model)下被证明是安全的。随机预言模型作为一种理想化的计算模型，是由Bellare和Rogaway于1993年提出的。在这个模型中，任何具体的对象例如哈希函数，都被当作随机对象。它允许人们规约参数到相应的计算，哈希函数被作为一个随机预言返回值，对每一个新的询问，将得到一个随机的应答。但在具体的数字签名方案中，因为使用的哈希函数是具体的，对于询问的应答结果不一定是随机的，这就有可能导致方案的不安全[12,13,14]。而另一方面，不需要随机预言模型(Without Random Oracle Model)的证明，即在标准模型(Standard Model)下的证明能够清楚地表明，除非其所基于的困难问题被破解，否则一个可证安全的密码方案不可能被攻破。因此，如果我们在方案的安全证明过程中不依赖理想化的随机预言模型，那么该方案的安全性证明将能够提供更充分的保障[15]。因此，设计在标准模型下可证安全的基于身份的数字签名方案是本文研究工作的动机之一。
1 引言
2 预备知识
3 基于身份的高效签名方案
4 安全性分析
5 方案比较
6 结束语
参考文献：
Shamir A. Identity-based cryptosystems and signature schemes. Crypto’1984, Santa Barbara, CA, Aug.1984, 47-53
Boneh D, Franklin M. Identity-based encryption from the Weil pairing. Crypto’2001, Springer-Verlag, 2001, LNCS 2139, 213-229
Sakai R, Ohgishi K, Kasahara M. Cryptosystems based on pairing. Symposium on Cryptography and Information Security, SCIS’2000, 26-28
Paterson K G. ID-based signatures from pairings on elliptic curves. Cryptology ePrint Archive, Report 2002/003, 2002
Chen X, Zhang F, Kim K. A new ID-based group signature scheme from bilinear pairings. WISA’2003, Springer-Verlag, 2003, LNCS 2908, 585-592
Hess F. Efficient identity based signature schemes based on pairings. SAC’2002, Springer-Verlag, 2003, LNCS 2595, 310-324
Cha J C, Cheon J H. An identity-based signature from gap Diffie-Hellman groups. PKC’2003, Springer-Verlag, 2003, LNCS 2567, 18-30
Yi X. An identity-based signature scheme from the Weil pairing. IEEE Communications Letters. 2003, 7(2): 76-78
Yoon H, Cheon J H, Kim.Y. Batch verifications with ID-based signatures. ICISC’2004, Springer-Verlag, 2005, LNCS 3506, 233-248
LI Jin, ZHANG FangGuo, WANG YanMing. Two Efficient Hierarchical Identity Based Signature Schemes. ACTA Electronic Sinica, 2007, 35(1):150-152(in Chinese) (李进,张方国,王燕鸣.两个高效的基于分级身份的签名方案.电子学报,2007, 35(1):150-152)
Bellare M, Rogoway P. Random oracles are practical: A paradigm for designing efficient protocols. Proceedings of the First Conference on Computer and Communications Security, ACM, 1993, 62-73
Canetti R, Goldreich O, Halevi S. The random oracle methodology, Revisited (preliminary version). Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. STOC’98, ACM, New York, 209-218
Bellare M, Boldyreva A, Palacio A. A uninstantiable random oracle-model scheme for a hybrid-encryption problem. In: C. Cachin and J. Camenisch (eds.), EUROCRYPT’2004, Springer, 2004, LNCS 3027, 171-188
FENG DengGuo. Research on Theory and Approach of Provable Security. Journal of Software 2005, 16(10): 1743-1756. (in Chinese) (冯登国.可证明安全性理论与方法研究.软件学报, 2005, 16(10): 1743-1756)
[15] WANG ShengBao, CAO ZhenFu, DONG XiaoLei. Provably Secure Identity-Based Authenticated Key Agreement Protocols in the Standard Model. Chinese Journal of Computers, 2007, 30(10): 1842-1852. (in Chinese) (王圣宝,曹珍富,董晓蕾. 标准模型下可证安全的身份基认证密钥协商协议.计算机学报, 2007, 30(10): 1842-1852)
[16] Boneh D, Boyen X. Efficient selective-ID secure identity-based encryption without random oracles. In: C. Cachin and J. Camenisch (eds.), EUROCRYPT’2004, Springer, 2004, LNCS 3027, 223-238
[17] Boneh D and Boyen X. Secure identity based encryption without random oracles. In M. K. Franklin, editor, CRYPTO’2004, Springer, 2004, LNCS 3152, 443-459
[18] Waters B. Efficient identity-based encryption without random oracles. In R.Cramer, editor, EUROCRYPT’2005, Springer, 2005, LNCS 3494, 114-127
[19] Paterson K G, Schuldt J C N. Efficient identity-based signatures secure in the standard model. ACISP’2006, 2006. Springer-Verlag, 2006, LNCS 4058, 207-222
[20] Goldwasser S, Micali S, Rivest R L. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput 1988, 17(2), 281-308
[21] Boneh D, Boyen X. Short signatures without random oracles. In: C. Cachin and J. Camenisch (eds.), EUROCRYPT’2004, Springer, 2004, LNCS 3027, 56-73
[22] Chatterjee S, Sarkar P. Trading time for space: Towards an efficient IBE scheme with short(er) public parameters in the standard model. In: D. Won and S. Kim (eds.), ICISC’2005, Springer, 2006, LNCS 3935, 424-440
[23] Naccache D. Secure and practical identity-based encryption. Cryptology ePrint Archive, Report 2005/369, 2005. http://eprint.iacr.org/
[24] Li J G, Huang X Y, Mu Y, Susilo W, Wu Q H. Certificate-based signature: security model and efficient construction. EuroPKI’2007, Springer-Verlag, 2007, LNCS 4582, 110-125
[25] Kang B G, Park J H, Hahn S G. A certificate-based signature scheme. CT-RSA’04. Springer-Verlag, 2004, LNCS 2964, 99-111
[26] Wang L H, Shao J, Cao Z F, Mambo M, Yamamura A. A certificate-based proxy cryptosystem with revocable proxy decryption power. Indocrypt’2007, Springer-Verlag, 2007, LNCS 4859, 297-311
[27] Li J G, Huang X Y, Mu Y, Wu W. Cryptanalysis and improvement of an efficient certificateless signature scheme. Journal of Communications and Networks. 2008, 10(1): 10-17
[28] Lu Y, Li J G, Xiao J M. Constructing efficient certificate-based encryption with paring. Journal of Computers. 2009, 4 (1): 19-26
作者点评：
本文利用Waters方法，基于PS方案，提出一种在标准模型下安全的基于身份的高效签名方案。证明过程中的攻击模型和困难问题假设均没有变化，这说明本文的方案和PS方案具有同样的安全性。从上述方案比较可以看到：本文方案的通信代价和签名算法计算量与PS方案相当，本文方案将PS方案的验证算法的计算量减小了三分之一。在实际使用中可以将签名中始终不变的部分作为系统参数的一部分公开，签名长度可以减小三分之一。在这种情况下，本文方案的签名长度与Boneh和Boyen提出的短签名[21]长度相当，验证算法的计算量比他们的方案多一个 运算。但是Boneh和Boyen方案的安全性规约为非标准的强Diffie-Hellman假定，而本文方案的安全性可规约为经典的计算Diffie-Hellman假定。本文方案的主要缺点是PKG的系统参数过长（文献[18,19]也有同样的问题），事实上，PKG的系统参数 中的 是为了证明的需要，实际应用时可以省略，可以略微缩短PKG系统参数的长度。正如文献[19]所指出的那样，本文可以使用文献[22,23]的方法对方案进行改进，进一步减少PKG系统参数的长度。本文提出的方案可用于构造安全、高效的基于证书的签名和加密方案以及无证书的签名方案[24-28]。