Abstract
Identity-based cryptography has been introduced by Shamir at Crypto’84 to avoid the use of expensive certificates in certified public key cryptography. In such system, the identity becomes the public key and each user needs to interact with a designated authority to obtain the related private key. It however suffers the key escrow problem since the authority knows the private keys of all users. To deal with this problem, Riyami and Paterson have introduced, at Asiacrypt’03, the notion of certificateless public key cryptography. In this case, there is no need to use the certificate to certify the public key, and neither the user nor the authority can derive the full private key by himself. There have been several efforts to propose a certificateless signature (\(\mathsf {CLS}\)) scheme in the standard model, but all of them either make use of the Waters’ technique or of the generic conversion technique (proposed by Yum and Lee at ACISP’04 and later modified by Hu et al. at ACISP’06) which both lead to inefficient schemes. In this paper, we introduce a new and direct approach to construct a \(\mathsf {CLS}\) scheme, secure in the standard model, with constant-size of all parameters and having efficient computing time. Our scheme is therefore very efficient when comparing to existing \(\mathsf {CLS}\) schemes in the standard model.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Al-Riyami, S.S., Paterson, K.G.: Certificateless public key cryptography. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 452–473. Springer, Heidelberg (2003). doi:10.1007/978-3-540-40061-5_29
Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptology 21(2), 149–177 (2008)
Chatterjee, S., Sarkar, P.: Trading time for space: towards an efficient IBE scheme with short(er) public parameters in the standard model. In: Won, D.H., Kim, S. (eds.) ICISC 2005. LNCS, vol. 3935, pp. 424–440. Springer, Heidelberg (2006). doi:10.1007/11734727_33
Choi, K.Y., Park, J.H., Hwang, J.Y., Lee, D.H.: Efficient certificateless signature schemes. In: Katz, J., Yung, M. (eds.) ACNS 2007. LNCS, vol. 4521, pp. 443–458. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72738-5_29
Galbraith, S.D., Paterson, K.G., Smart, N.P.: Pairings for cryptographers. Discrete Appl. Math. 156(16), 3113–3121 (2008)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Hu, B.C., Wong, D.S., Zhang, Z., Deng, X.: Key replacement attack against a generic construction of certificateless signature. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 235–246. Springer, Heidelberg (2006). doi:10.1007/11780656_20
Huang, X., Mu, Y., Susilo, W., Wong, D.S., Wu, W.: Certificateless signatures: New schemes and security models. Comput. J. 55(4), 457–474 (2012)
Huang, X., Susilo, W., Mu, Y., Zhang, F.: On the security of certificateless signature schemes from Asiacrypt 2003. In: Desmedt, Y.G., Wang, H., Mu, Y., Li, Y. (eds.) CANS 2005. LNCS, vol. 3810, pp. 13–25. Springer, Heidelberg (2005). doi:10.1007/11599371_2
Liu, J., Au, M., Susilo, W., Self-generated-certificate public key cryptography and certificateless signature, encryption scheme in the standardmodel. In: Proceeding 2007 ACM Symposium Information, Singapore (2007)
Naccache, D.: Secure and practical identity-based encryption. Cryptology ePrint Archive, Report 2005/369 (2005)
Pointcheval, D., Sanders, O.: Short randomizable signatures. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 111–126. Springer, Heidelberg (2016). doi:10.1007/978-3-319-29485-8_7
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985). doi:10.1007/3-540-39568-7_5
Tso, R., Yi, X., Huang, X.: Efficient and short certificateless signature. In: Franklin, M.K., Hui, L.C.K., Wong, D.S. (eds.) CANS 2008. LNCS, vol. 5339, pp. 64–79. Springer, Heidelberg (2008). doi:10.1007/978-3-540-89641-8_5
Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). doi:10.1007/11426639_7
Xia, Q., Xu, C., Yu, Y.: Key replacement attack on two certificateless signature schemes without random oracles. Key Eng. Mater. 2010 439, 1606–1611 (2010)
Xiong, H., Qin, Z., Li, F.: An improved certificateless signature scheme secure in the standard model. Fundamenta Informaticae (2008)
Yu, Y., Mu, Y., Wang, G., Xia, Q., Yang, B.: Improved certificateless signature scheme provably secure in the standard model. IET Inf. Secur. 6(2), 102–110 (2012). ISSN 1751–8709
Yuan, Y., Li, D., Tian, L., Zhu, H.: Certificateless signature scheme without random oracles. In: Park, J.H., Chen, H.-H., Atiquzzaman, M., Lee, C., Kim, T., Yeo, S.-S. (eds.) ISA 2009. LNCS, vol. 5576, pp. 31–40. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02617-1_4
Yum, D.H., Lee, P.J.: Generic construction of certificateless signature. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 200–211. Springer, Heidelberg (2004). doi:10.1007/978-3-540-27800-9_18
Zhang, Z., Wong, D.S., Xu, J., Feng, D.: Certificateless public-key signature: security model and efficient construction. In: Zhou, J., Yung, M., Bao, F. (eds.) ACNS 2006. LNCS, vol. 3989, pp. 293–308. Springer, Heidelberg (2006). doi:10.1007/11767480_20
Acknowledgement
This work was partially conducted within the context of the Vietnamese Project Pervasive and Secure Information Service Infrastructure for Internet of Things based on Cloud Computing.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Proof of Assumption 2 in Bilinear Generic Group
A Proof of Assumption 2 in Bilinear Generic Group
Assume that \(q\in \mathbb {Z}\) is the maximum number of queries the adversary can make to the oracle \(\mathcal {O}_1\) or \(\mathcal {O}_2\). The adversary then will get the inputs from the group \(\mathbb {G}\) and \(\tilde{\mathbb {G}}\). For the group \(\widetilde{\mathbb {G}}\), the adversary has:
For the group \(\mathbb {G}\), the adversary has:
where \(\mathsf {ID}^* = \mathsf {ID}_t, m^* = m_t\). We need to prove that simultaneously from P, the adversary cannot lead to \(\frac{y}{r^*}\) and from Q the adversary cannot lead to the triplet
Assume that \(B_1, B_2, B_3\) are linear combinations of elements in Q which lead to the triplet
therefore, we have equations
From the first equation, it is easy to realize that in \(B_2\) we cannot have elements
since in \(B_1\) the highest degree of variables x, y are 1 and \(r_{i,j}\) are unknown random constants.
From the second equation, we cannot have element 1 in \(B_2\), since the highest degree of variable s in \(B_3\) is \(-1\). Overall, the adversary should find constants \(\{c_i\}_{i\in [q]\atop i \ne t}, \{d_{i,j}\}_{(i,j)\in [\sqrt{q}]\times [\sqrt{q}]\atop (i,j)\ne (t,t)}\) to produce \(B_2\). This means that:
On the other hand, assume that A is a linear combination of elements in P which leads to \(\frac{y}{r^*}\), which means that
The main point is that we cannot have the elements x, s and 1 and the above equation hold for all x, y, s and unknown random constants \(r_{i,j}\). We thus transform it as
and then
where \(a, \{b_{i,j}\}_{(i,j)\in [\sqrt{q}]\times [\sqrt{q}]\atop (i,j)\ne (t,t)}\) are constants. From the equation above we see that to make the equation hold for all s and unknown random constants \(r_{i,j}\), the constants a and \(c_i\) must be equal 0. So, the Eq. (1) is rewritten as follows
Since \(r_{i,j}\) are unknown random constants, \(B_1\) must contain the elements related to \(r_{i,j}\), or the above equation should be rewritten with \(d'_{i,j}, k_{i,j}\) as constants.
Since in the left side of the equation \(j \ne t\), that means the adversary cannot find \(d_{t,j}, d'_{t,j}, k_{t,j}\) such that \(d_{t,j}.r_{t,j}.(x+m^*.y)-d'_{t,j}.r_{t,j}.(x+m_j.y)+k_{t,j}.r_{t,j} = 0\) for all \(x,y, r_{t,j}\). On the other hand, the elements \(r_{t,j}\) do not appear in the right side of the equation, that means one cannot find the constants \(d_{t,j}, d'_{t,j}, k_{t,j}\) such that the above equation hold for all unknown random elements \(r_{t,j}\), or simultaneously from P the adversary cannot lead to \(\frac{y}{r^*}\) and from Q the adversary cannot lead to the triplet
which concludes our proof. \(\square \)
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Canard, S., Trinh, V.C. (2016). An Efficient Certificateless Signature Scheme in the Standard Model. In: Ray, I., Gaur, M., Conti, M., Sanghi, D., Kamakoti, V. (eds) Information Systems Security. ICISS 2016. Lecture Notes in Computer Science(), vol 10063. Springer, Cham. https://doi.org/10.1007/978-3-319-49806-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-49806-5_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49805-8
Online ISBN: 978-3-319-49806-5
eBook Packages: Computer ScienceComputer Science (R0)