A new key-insulated signature scheme

In this paper we propose a new strong and perfectly key insulated signature scheme, more efficient than previous proposals and whose key length is constant and independent of the number of insulated time periods. Moreover, unlike previous schemes, it becomes forward secure when all the existing secrets at a given time period are compromised. We also present a variant forward-secure scheme in which an adversary needs to compromise a user at a second time period before being able to compute future secret keys.