Strong Key-Insulated Signature Schemes

  • Yevgeniy Dodis
  • Jonathan Katz
  • Shouhuai Xu
  • Moti Yung
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)


Signature computation is frequently performed on insecure devices—e.g., mobile phones — operating in an environment where the private (signing)k ey is likely to be exposed. Strong key-insulated signature schemes are one way to mitigate the damage done when this occurs. In the key-insulated model [6], the secret key stored on an insecure device is refreshed at discrete time periods via interaction with a physically-secure device which stores a “master key”. All signing is still done by the insecure device, and the public key remains fixed throughout the lifetime of the protocol. In a strong (t,N)-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods is unable to forge signatures for any of the remaining N-t periods. Furthermore, the physically-secure device (or an adversary who compromises only this device)is unable to forge signatures for any time period.

We present here constructions of strong key-insulated signature schemes based on a variety of assumptions. First, we demonstrate a generic construction of a strong (N— 1,N)-key-insulated signature scheme using any standard signature scheme. We then give a construction of a strong (t,N)-signature scheme whose security may be based on the discrete logarithm assumption in the random oracle model. This construction offers faster signing and verification than the generic construction, at the expense of O(t)k ey update time and key length. Finally, we construct strong (N —1,N)-key-insulated schemes based on any “trapdoor signature scheme” (a notion we introduce here); our resulting construction in fact serves as an identity-based signature scheme as well. This leads to very efficient solutions based on, e.g., the RSA assumption in the random oracle model.


Signature Scheme Random Oracle Random Oracle Model Secure Device Signing Oracle 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


  1. [1]
    M. Abdalla and M. Bellare. Rekeyed Digital Signature Schemes: Damage-Containment in the Face of Key Exposure. Manuscript. July, 2001. 132, 134Google Scholar
  2. [2]
    R. Anderson. Invited lecture, CCCS’ 97. 133Google Scholar
  3. [3]
    M. Bellare and S.K. Miner. A Forward-Secure Digital Signature Scheme. Crypto’ 99. 133, 134Google Scholar
  4. [4]
    J. Cha and J. Cheon. An Identity-based Signature Scheme from Gap Diffie-Hellman Groups. Available at 132, 142
  5. [5]
    J. Cheon. A Universal Forgery of Hess’s Second ID-based Signature against the Known-message Attack. Available at 142
  6. [6]
    Y. Dodis, J. Katz, S. Xu and M. Yung. Key-Insulated Public-Key Cryptosystems. Eurocrypt 2002. 130, 131, 132, 134, 135Google Scholar
  7. [7]
    Y. Dodis and L. Reyzin. On the Power of Claw-Free Permutations. SCN 2002. 141Google Scholar
  8. [8]
    A. Fiat and A. Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. Crypto’ 86. 141Google Scholar
  9. [9]
    R. Gennaro, T. Rabin, S. Jarecki, and H. Krawczyk. Robust and Efficient Sharing of RSA Functions. J. Crypto 13(2): 273–300 (2000). 142zbMATHCrossRefMathSciNetGoogle Scholar
  10. [10]
    M. Girault. Relaxing Tamper-Resistance Requirements for Smart Cards Using (Auto)-Proxy Signatures. CARDIS’ 98. 132Google Scholar
  11. [11]
    O. Goldreich, B. Pfitzmann, and R. L. Rivest. Self-Delegation with Controlled Propagation — or — What if You Lose Your Laptop? Crypto’ 98. 133Google Scholar
  12. [12]
    S. Goldwasser, S. Micali, and R.L. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Computing 17(2): 281–308 (1988).zbMATHCrossRefMathSciNetGoogle Scholar
  13. [13]
    L. C. Guillou and J.-J. Quisquater. A Practical Zero-Knowledge Protocol Fitted to Security Microprocessors Minimizing Both Transmission and Memory. Eurocrypt’ 88. 134, 141Google Scholar
  14. [14]
    F. Hess. Exponent Group Signature Schemes and Efficient Identity Based Signature Schemes Based on Pairings. Available at 2002/012/. 132, 142
  15. [15]
    G. Itkis. Intrusion-Resilient Signatures: Generic Constructions, or Defeating Strong Adversary with Minimal Assumptions. SCN 2002. 133Google Scholar
  16. [16]
    G. Itkis and L. Reyzin. SiBIR: Signer-Base Intrusion-Resilient Signatures. Crypto 2002. 133, 136Google Scholar
  17. [17]
    A. Joux and K. Nguyen. Separating Decision Diffie-Hellman from Diffie-Hellman in Cryptographic Groups. Available at 142
  18. [18]
    J. Katz and M. Yung. Threshold Crytptosystems Based on Factoring. Asiacrypt 2002. 142Google Scholar
  19. [19]
    C.-F. Lu and S.W. Shieh. Secure Key-Evolving Protocols for Discrete Logarithm Schemes. RSA 2002. 132Google Scholar
  20. [20]
    S. Micali. A Secure and Efficient Digital Signature Algorithm. Technical Report MIT/LCS/TM-501, MIT, 1994. 141Google Scholar
  21. [21]
    K. Ohta and T. Okamoto. On Concrete Security Treatment of Signatures Derived from Identification. Crypto’ 98. 139Google Scholar
  22. [22]
    T. Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. Crypto’ 92. 139Google Scholar
  23. [23]
    H. Ong and C. Schnorr. Fast Signature Generation with a Fiat-Shamir-Like Scheme. Eurocrypt’ 90. 134, 141Google Scholar
  24. [24]
    K. Paterson. ID-based Signatures from Pairings on Elliptic Curves. Available at 132, 142
  25. [25]
    R. Sakai, K. Ohgishi, M. Kasahara. Cryptosystems based on pairing. SCIC 2001.132, 142Google Scholar
  26. [26]
    C.P. Schnorr. Efficient Signature Generation by Smart Cards. J. Crypto 4(3): 161–174 (1991). 139zbMATHMathSciNetCrossRefGoogle Scholar
  27. [27]
    C.P. Schnorr. Security of 2t-root Identification and Signatures. Crypto’ 96. 141Google Scholar
  28. [28]
    A. Shamir. Identity-Based Cryptosystems and Signature Schemes. Crypto’ 84. 134, 142Google Scholar
  29. [29]
    V. Shoup. On the Security of a Practical Identification Scheme. J. Crypto 12(4): 247–160 (1999). 141zbMATHCrossRefMathSciNetGoogle Scholar
  30. [30]
    W.-G. Tzeng and Z.-J. Tzeng. Robust Key-Evolving Public Key Encryption Schemes. Available at 132

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Yevgeniy Dodis
    • 1
  • Jonathan Katz
    • 2
  • Shouhuai Xu
    • 3
  • Moti Yung
    • 4
  1. 1.Department of Computer ScienceNew York UniversityUSA
  2. 2.Department of Computer ScienceUniversity of Maryland (College Park)USA
  3. 3.Department of Information and Computer ScienceUniversity of California at IrvineUSA
  4. 4.Department of Computer ScienceColumbia UniversityUSA

Personalised recommendations