Signature computation is frequently performed on insecure devices—eg, 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