Strong Key-Insulated Signature Schemes

Authors: Yevgeniy Dodis, Jonathan Katz, Shouhuai Xu and Moti Yung

ABSTRACT

Signature computation is frequently performed on insecure devices --- e.g., mobile phones --- operating in an environment where the private (signing) key 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 \cite{DKXY02}, 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 \emph{any} time period.

We present here constructions of strong key-insulated signature schemes based on a variety of assumptions. First, we demonstrate %and prove secure a generic construction of a strong $(N-1, N)$-key-insulated signature scheme using any standard signature scheme. We then give a %an improved 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)$ key update time and key length. % We then give an improved construction of a strong $(t, N)$-signature %scheme whose security may be based on the discrete logarithm %assumption in the random oracle model. 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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-25.ps.gz