Abstract
This paper proposes a new public key authenticated encryption (signcryption) scheme based on the hardness of q-Diffie-Hellman problems in Gap Diffie-Hellman groups. This new scheme is quite efficient: the signcryption operation has almost the same cost as an El Gamal encryption while the reverse operation only requires one pairing evaluation and three exponentiations. The scheme’s chosen-ciphertext security is shown to be related to the hardness of the q-Diffie-Hellman Inversion (q–DHI) problem in the random oracle model while its unforgeability is proved under the q-Strong Diffie-Hellman assumption (q-SDH). It also provides detachable signatures that are unlinkable to the original anonymous ciphertext. We also show that most of the sender’s workload can be computed offline. Our construction is based on a signature scheme independently studied by Boneh-Boyen and Zhang et al. in 2004.
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
An, J.-H.: Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses (2001), eprint available at, http://eprint.iacr.org/2001/079/
An, J.-H., Dodis, Y., Rabin, T.: On the security of joint signature and encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 83–107. Springer, Heidelberg (2002)
Baek, J., Steinfeld, R., Zheng, Y.: Formal Proofs for the Security of Signcryption. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 80–98. Springer, Heidelberg (2002)
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)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: 1st ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Boneh, D., Boyen, X.: Short Signatures Without Random Oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56–73. Springer, Heidelberg (2004)
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)
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–532. 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)
Dodis, Y., Freedman, M.-J., Jarecki, S., Walfish, S.: Versatile Padding Schemes for Joint Signature and Encryption. In: ACM Conference on Computer and Communication Security (CCS) (October 2004) (to appear)
El Gamal, T.: A Public Key Cryptosystem and Signature Scheme Based on Discrete Logarithms. IEEE Trans. on Information Theory 31 (1985)
Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 537–554. Springer, Heidelberg (1999)
Jeong, I.-R., Jeong, H.-Y., Rhee, H.-S., Lee, D.-H., Jong, I.-L.: Provably secure encrypt-then-sign composition in hybrid signcryption. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 16–34. Springer, Heidelberg (2003)
Joux, A., Nguyen, K.: Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups (2001), available at http://eprint.iacr.org/2001/003/
Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: 10th ACM Conference on Computer and Communications Security, pp. 155–164 (2003)
Libert, B., Quisquater, J.-J.: Efficient Signcryption with Key Privacy from Gap Diffie-Hellman Groups. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 187–200. Springer, Heidelberg (2004)
Malone-Lee, J.: Signcryption with non-repudiation, Technical report (2002), available at http://www.cs.bris.ac.uk/Tools/Reports/Ps/2002-malonelee.pdf
Malone-Lee, J., Mao, W.: Two birds one stone: Signcryption using RSA. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 211–225. Springer, Heidelberg (2003)
Mitsunari, S., Sakai, R., Kasahara, M.: A new traitor tracing. IEICE Trans. E85-A(2), 481–484 (2002)
Miyaji, A., Nakabayashi, M., Tanako, S.: New Explicit Conditions of Elliptic Curve Traces for FR-Reduction. IEICE Trans. Fundamentals E84-A(5), 1234–1243 (2001)
M’Raïhi, D., Naccache, D., Pointcheval, D., Vaudenay, S.: Computational Alternatives to Random Number Generators. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 72–80. Springer, Heidelberg (1999)
Okamoto, T., Pointcheval, D.: The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, Springer, Heidelberg (2001)
Pieprzyk, J., Pointcheval, D.: Parallel Authentication and Public-Key Encryption. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 383–401. Springer, Heidelberg (2003)
Shin, J.-B., Lee, K., Shim, K.: New DSA-verifiable signcryption schemes. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp. 35–47. Springer, Heidelberg (2002)
Steinfeld, R., Zheng, Y.: A signcryption scheme based on integer factorization. In: Okamoto, E., Pieprzyk, J.P., Seberry, J. (eds.) ISW 2000. LNCS, vol. 1975, pp. 308–322. Springer, Heidelberg (2000)
Yum, D.-H., Lee, P.-J.: New signcryption schemes based on KCDSA. In: Kim, K.-c. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 305–317. Springer, Heidelberg (2001)
Zhang, F., Safavi-Naini, R., Susilo, W.: An Efficient Signature Scheme from Bilinear Pairings and Its Applications. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 277–290. Springer, Heidelberg (2004)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Libert, B., Quisquater, JJ. (2005). Improved Signcryption from q-Diffie-Hellman Problems. In: Blundo, C., Cimato, S. (eds) Security in Communication Networks. SCN 2004. Lecture Notes in Computer Science, vol 3352. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30598-9_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-30598-9_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24301-4
Online ISBN: 978-3-540-30598-9
eBook Packages: Computer ScienceComputer Science (R0)