Strong key-insulated signature schemes

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 [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) key 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.