Identity-Based Key-Insulated Signature with Secure Key-Updates

  • Jian Weng
  • Shengli Liu
  • Kefei Chen
  • Xiangxue Li
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


Standard identity-based (ID-based) signature schemes typically rely on the assumption that secret keys are kept perfectly secure. However, with more and more cryptographic primitives are deployed on insecure devices (e.g. mobile devices), key-exposure seems inevitable. This problem is perhaps the most devastating attack on a cryptosystem since it typically means that security is entirely lost. To minimize the damage caused by key-exposure in ID-based signatures scenarios, Zhou et al. [32] applied Dodis et al.’s key-insulation mechanism [12] and proposed an ID-based key-insulated signature (IBKIS) scheme. However, their scheme is not strong key-insulated, i.e, if an adversary compromises the helper key, he can derive all the temporary secret keys and sign messages on behalf the legitimate user. In this paper, we re-formalize the definition and security notions for IBKIS schemes, and then propose a new IBKIS scheme with secure key-updates. The proposed scheme is strong key-insulated and perfectly key-insulated. Our scheme also enjoys desirable properties such as unbounded number of time periods and random-access key-updates.


Key-Insulated Identity-Based Signature Key-Exposure Bilinear Pairings 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Anderson, R.: Two Remarks on Public-Key Cryptology. Invited lecture. In: CCCS 1997 (1997), Available at:
  2. 2.
    Barreto, P.: The pairing-based crypto lounge,
  3. 3.
    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)CrossRefGoogle Scholar
  4. 4.
    Bellare, M., Miner, S.: A Forward-Secure Digital Signature Scheme. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 431–448. Springer, Heidelberg (1999)Google Scholar
  5. 5.
    Bellare, M., Palacio, A.: Protecting against Key Exposure: Strongly Key-Insulated Encryption with Optimal Threshold, Available at:
  6. 6.
    Cao, Z.: Universal Forgeability of Wang-Wu-Wang Key-Insulated Signature Scheme, Available at:
  7. 7.
    Cha, J.C., Cheon, J.H.: An Identity-Based Signature from Gap Diffie-Hellman Groups. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 18–30. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  8. 8.
    Cheon, J.H., Hopper, N., Kim, Y., Osipkov, I.: Authenticated Key-Insulated Public Key Encryption and Timed-Release Cryptography, Available at:
  9. 9.
    Coron, J.-S.: On the Exact Security of Full Domain Hash. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 229–235. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  10. 10.
    Desmedt, Y., Frankel, Y.: Threshold Cryptosystems. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 307–315. Springer, Heidelberg (1990)Google Scholar
  11. 11.
    Dodis, Y., Katz, J., Xu, S., Yung, M.: Strong key-insulated signature schemes. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 130–144. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  12. 12.
    Dodis, Y., Katz, J., Xu, S., Yung, M.: Key-Insulated Public-Key Cryptosystems. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 65–82. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  13. 13.
    Dodis, Y., Yung, M.: Exposure-Resilience for Free: The Hierarchical ID-based Encryption Case. In: Proc. of IEEE Security in Storage Workshop 2002, pp. 45–52 (2002)Google Scholar
  14. 14.
    Gentry, C., Silverberg, A.: Hierarchical ID-Based Cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548–566. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  15. 15.
    González-Deleito, N., Markowitch, O., Dall’Olio, E.: A New Key-Insulated Signature Scheme. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 465–479. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  16. 16.
    Hess, F.: Efficient Identity Based Signature Schemes Based on Pairings. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 310–324. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  17. 17.
    Hanaoka, G., Hanaoka, Y., Imai, H.: Parallel key-insulated public key encryption. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 105–122. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  18. 18.
    Hanaoka, Y., Hanaoka, G., Shikata, J., Imai, H.: Unconditionally Secure Key Insulated Cryptosystems: Models, Bounds and Constructions. In: Deng, R.H., Qing, S., Bao, F., Zhou, J. (eds.) ICICS 2002. LNCS, vol. 2513, pp. 85–96. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  19. 19.
    Hanaoka, Y., Hanaoka, G., Shikata, J., Imai, H.: Identity-based hierarchical strongly keyinsulated encryption and its application. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 495–514. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  20. 20.
    Horwitz, J., Lynn, B.: Towards Hierarchical Identity-Based Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 466–481. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  21. 21.
    Itkis, G., Reyzin, L.: SiBIR: Signer-Base Intrusion- Resilient Signatures. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 499–514. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  22. 22.
    Le, Z., Ouyang, Y., Ford, J., Makedon, F.: A Hierarchical Key-Insulated Signature Scheme in the CA Trust Model. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 280–291. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  23. 23.
    Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks. In: Proc. of PODC 1991, pp. 51–59. ACM Press, New York (1991)CrossRefGoogle Scholar
  24. 24.
    Paterson, K.G.: ID-Based Signatures from Pairings on Elliptic Curves. IEEE Communications Letters 38(18), 1025–1026 (2002)Google Scholar
  25. 25.
    De Santis, A., Desmedt, Y., Frankel, Y., Yung, M.: How to Share a Function Securely. In: Proc. of STOC 1994, pp. 522–533. ACM Press, New York (1994)Google Scholar
  26. 26.
    Shamir, A.: How to Share a Secret. Comm. of the ACM 22(11), 612–613 (1979)zbMATHCrossRefMathSciNetGoogle Scholar
  27. 27.
    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)CrossRefGoogle Scholar
  28. 28.
    Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: Proc. of SCIS 2000, pp. 26–28 (2000)Google Scholar
  29. 29.
    Wang, J., Wu, Q., Wang, Y.: A New Perfect and Strong Key-Insulated signature scheme. In: Proc. of ChinaCrypt 2004, pp. 233–239 (2004)Google Scholar
  30. 30.
    Yi, X.: An Identity-Based Signature Scheme from the Weil Pairing. IEEE Communications Letters 7(2) (2003)Google Scholar
  31. 31.
    Yum, D.H., Lee, P.J.: Efficient key updating signature schemes based on IBS. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 16–18. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  32. 32.
    Zhou, Y., Cao, Z., Chai, Z.: Identity Based Key Insulated Signature. In: Chen, K., Deng, R., Lai, X., Zhou, J. (eds.) ISPEC 2006. LNCS, vol. 3903, pp. 226–234. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  33. 33.
    Zhang, F., Kim, K.: ID-based blind signature and ring signature from pairings. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 533–547. Springer, Heidelberg (2002)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Jian Weng
    • 1
  • Shengli Liu
    • 1
    • 2
  • Kefei Chen
    • 1
  • Xiangxue Li
    • 1
  1. 1.Dept. of Computer Science and EngineeringShanghai Jiao Tong UniversityShanghaiChina
  2. 2.Key Laboratory of CNISXidian UniversityXianP.R. China

Personalised recommendations