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
DIMACS Home Page