Abstract
A digital signature with message recovery is a signature that the message itself is not required to be transmitted together with the signature. Comparing with other (non-short) digital signatures, it has the advantage of small data size of communication. This kind of signature schemes have been widely investigated a decade ago, but, no ID-based message recovery signature is proposed until 2005 by Zhang et al. Since, up to the present, no method can be used to shorten ID-based signatures directly, ID-based message recovery signatures are regarded as a useful method to shorten ID-based signatures, in contrast to proposing a short signature scheme. In this paper, two new ID-based signature schemes with message recovery are proposed. The first one can deal with messages of fixed length and the second one can deal with messages of arbitrary length. Similar to Zhang et al.’s schemes, our schemes shows the idea of shortening ID-based signatures. However, our schemes are more efficient than Zhang et al.’s schemes. In addition, after comparing with Boneh et al.’s short signature (which is not ID-based), we find that although the communication cost is still a little larger than that of a short signature, the computational cost of our scheme is less than that of Boneh et al.’s short signature in the verification phase and our schemes surpass a short signature scheme in the concept of ID-based property. Under the hardness of k-BDHI problem, our schemes are proven secure in the random oracle model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abe, M., Okamoto, T.: A signature scheme with message recovery as secure as discrete logarithm. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 378–389. Springer, Heidelberg (1999)
Bao, F., Deng, R.H.: A signcryption scheme with signature directly verifiable by public key. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol. 1431, pp. 55–59. Springer, Heidelberg (1998)
Barr, K., Asanovic, K.: Energy aware lossless data compression. In: MobiSys 2003. Proceedings of the ACM Conference on Mobile Systems, Applications, and Services (2003)
Barreto, P.S.L.M., Libert, B., McCullagh, N., Quisquater, J.: Efficient and provably-secure identity-based signatures and signcryption from bilinear maps. In: Atkinson, C., Bunse, C., Gross, H.-G., Peper, C. (eds.) ASIACRYPT 2005. LNCS, vol. 3778, pp. 515–532. Springer, Heidelberg (2005)
Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Proceedins of the 13th ACM Confetence on Computer and Communication Security, pp. 390–398 (2006)
Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–533. Springer, Heidelberg (2001)
Boyen, X.: Multipurpose identity-based signcryption: a Swiss army knife for identity-based cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 382–398. Springer, Heidelberg (2003)
Chen, K.: Signature with message recovery. Electronics Leters 34(20), 1934 (1998)
Chen, L., Lee, J.M.: Improved identity-based signcryption. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 362–379. Springer, Heidelberg (2005)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing 17(2), 281–308 (1988)
Horster, P., Michels, M., Petersen, H.: Authenticated encyprtion scheme with low communication costs. Electronics Letters 30(15), 1212–1213 (1994)
Lee, W.-B., Chang, C.-C.: Publicly verifiable authenticated encryption. Electronics Letters 31(19), 1656–1657 (1995)
Miyaji, A.: A message recovery signature scheme equivalent to DSA over elliptic curves. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 1–14. Springer, Heidelberg (1996)
Nyberg, K., Tuepple, R.A.: A new signature scheme based on the DSA giving message recovery. In: Proceedings of the 1st ACM conference on communication and computer security, pp. 58–61 (1993)
Nyberg, K., Ruepple, R.A.: Message recovery for signature schemes based on the discrete logarithm problem. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 182–193. Springer, Heidelberg (1995)
Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361–396 (2000)
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM 21, 120–126 (1978)
Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
Yeun, C.Y.: Digital signature with message recovery and authenticated encryption (signcryption)- a comparison. In: Walker, M. (ed.) Cryptography and Coding. LNCS, vol. 1746, pp. 307–312. Springer, Heidelberg (1999)
Zhang, F., Susilo, W., Mu, Y.: Identity-based partial message recovery signatures (or How to shorten ID-based signatures). In: Patrick, A.S., Yung, M. (eds.) FC 2005. LNCS, vol. 3570, pp. 45–56. Springer, Heidelberg (2005)
Zheng, Y.: Digital signcryption or how to achieve cost (signature & encryption < < cost (signature) + cost (encryption). In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 165–179. Springer, Heidelberg (1997)
Boneh, D., Boyen, X.: Efficient Selective ID Secure Identity Based Encryption without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tso, R., Gu, C., Okamoto, T., Okamoto, E. (2007). Efficient ID-Based Digital Signatures with Message Recovery. In: Bao, F., Ling, S., Okamoto, T., Wang, H., Xing, C. (eds) Cryptology and Network Security. CANS 2007. Lecture Notes in Computer Science, vol 4856. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76969-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-76969-9_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76968-2
Online ISBN: 978-3-540-76969-9
eBook Packages: Computer ScienceComputer Science (R0)