Advertisement

Efficient Intrusion-Resilient Signatures Without Random Oracles

  • Benoît Libert
  • Jean-Jacques Quisquater
  • Moti Yung
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)

Abstract

Intrusion-resilient signatures are key-evolving protocols that extend the concepts of forward-secure and key-insulated signatures. As in the latter schemes, time is divided into distinct periods where private keys are periodically updated while public keys remain fixed. Private keys are stored in both a user and a base; signature operations are performed by the user while the base is involved in periodic updates. Such a system remains secure after arbitrarily many compromises of both modules as long as break-ins are not simultaneous. Besides, when they simultaneously occur within some time period, past periods remain safe. In this work, we propose the first intrusion-resilient signature in the standard model (i.e. without random oracles) which provides both short signatures and at most log-squared private storage in the number of time periods.

Keywords

Intrusion-resilience standard model signatures pairings 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Abdalla, M., Miner, S.K., Namprempre, C.: Forward-Secure Threshold Signature Schemes. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 441–456. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  2. 2.
    Abdalla, M., Reyzin, L.: A New Forward-Secure Digital Signature Scheme. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 116–129. Springer, Heidelberg (1999)Google Scholar
  3. 3.
    Anderson, R.: Two Remarks on Public Key Cryptology. In: ACM Conference on Computer and Communications Security (1997) (Invited lecture)Google Scholar
  4. 4.
    Barreto, P.S.L.M., Naehrig, M.: Pairing-friendly elliptic curves of prime order. In: Preneel, B., Tavares, S. (eds.) SAC 2005. LNCS, vol. 3897, pp. 319–331. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  5. 5.
    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
  6. 6.
    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. ACM Press, New York (1993)Google Scholar
  7. 7.
    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)CrossRefGoogle Scholar
  8. 8.
    Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical Identity Based Encryption with Constant Size Ciphertext. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  9. 9.
    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
  10. 10.
    Boyen, X., Shacham, H., Shen, E., Waters, B.: Forward-Secure Signatures with Untrusted Update. In: ACM CCS 2006. ACM Press, New York (2006)Google Scholar
  11. 11.
    Camenisch, J., Koprowski, M.: Fine-grained forward-secure signature schemes without random oracles. Discrete Applied Mathematics 154(2), 175–188 (2006)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4), 557–594 (2004)CrossRefMathSciNetzbMATHGoogle Scholar
  13. 13.
    Canetti, R., Halevi, S., Katz, J.: A forward secure public key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 254–271. Springer, Heidelberg (2003)Google Scholar
  14. 14.
    Chow, S.S., Kwong Hui, L.C., Yiu, S.M., Chow, K.P.: Secure Hierarchical Identity Based Signature and Its Application. In: López, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol. 3269, pp. 480–494. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  15. 15.
    Dodis, Y., Franklin, M., Katz, J., Miyaji, A., Yung, M.: Intrusion-Resilient Public-Key Encryption. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 19–32. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  16. 16.
    Dodis, Y., Franklin, M., Katz, J., Miyaji, A., Yung, M.: A Generic Construction for Intrusion-Resilient Public-Key Encryption. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 81–98. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  17. 17.
    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
  18. 18.
    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
  19. 19.
    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
  20. 20.
    Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Comput. 17(2), 281–308 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Guillou, L., Quisquater, J.-J.: A “paradoxical” identity-based signature scheme resulting from zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 216–231. Springer, Heidelberg (1990)Google Scholar
  22. 22.
    Granger, R., Smart, N.P.: On Computing Products of Pairings. Cryptology ePrint Archive: Report 2006/172 (2006)Google Scholar
  23. 23.
    Herzberg, A., Jakobsson, M., Jarecki, S., Krawczyk, H., Yung, M.: Proactive Public Key and Signature Systems. In: 4th ACM Conference on Computer and Communication Security, pp. 100–110. ACM Press, New York (1997)CrossRefGoogle Scholar
  24. 24.
    Hu, F., Wu, C.-H., Irwin, J.D.: A New Forward Secure Signature Scheme using Bilinear Maps. Cryptology ePrint Archive: Report 2003/188 (2003)Google Scholar
  25. 25.
    Itkis, G., Reyzin, L.: Forward-Secure Signatures with Optimal Signing and Verifying. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 332–354. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  26. 26.
    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
  27. 27.
    Itkis, G.: Intrusion-Resilient Signatures: Generic Constructions, or Defeating Strong Adversary with Minimal Assumptions. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 102–118. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  28. 28.
    Itkis, G.: Forward Security: Adaptive Cryptography - Time Evolution. In: The Handbook of Information Security. John Wiley and Sons, Chichester (2004) (Invited)Google Scholar
  29. 29.
    Kang, B.G., Park, J.H., Hahn, S.G.: A New Forward Secure Signature Scheme. Cryptology ePrint Archive: Report 2004/183 (2004)Google Scholar
  30. 30.
    Katz, J.: A Forward-Secure Public-Key Encryption Scheme. Cryptology ePrint Archive: Report 2002/060 (2002)Google Scholar
  31. 31.
    Lamport, L.: Constructing Digital Signatures from a One-Way Function. Technical Report CSL-98. Sri Internation (1979)Google Scholar
  32. 32.
    Malkin, T., Micciancio, D., Miner, S.K.: Efficient Generic Forward-Secure Signatures with an Unbounded Number Of Time Periods. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 400–417. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  33. 33.
    Malkin, T., Obana, S., Yung, M.: The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 306–322. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  34. 34.
    Mambo, M., Usuda, K., Okamoto, E.: Proxy signatures for delegating signing operation. In: 3rd ACM Conference on Computer and Communications Security, pp. 48–57. ACM Press, New York (1996)CrossRefGoogle Scholar
  35. 35.
    Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICETransactions on Fundamentals E84-A(5), 1234–1243 (2001)Google Scholar
  36. 36.
    Ostrovsky, R., Yung, M.: How to Withstand Mobile Virus Attacks. In: 10th ACM Symp. on Principles of Distributed Computing, pp. 51–59 (1991)Google Scholar
  37. 37.
    Paterson, K.G., Schuldt, J.C.N.: Efficient Identity-based Signatures Secure in the Standard Model. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 207–222. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  38. 38.
    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
  39. 39.
    Waters, B.: Efficient Identity-Based Encryption Without Random Oracles. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  40. 40.
    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)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Benoît Libert
    • 1
  • Jean-Jacques Quisquater
    • 1
  • Moti Yung
    • 2
  1. 1.Microelectronics Laboratory, Crypto GroupUCLBelgium
  2. 2.RSA Labs and Columbia UniversityUSA

Personalised recommendations