Emerging applications like electronic commerce and secure communications over open networks have made clear the fundamental role of public key cryptography as a unique enabler for world-wide scale security solu- tions. On the other hand, these solutions clearly expose the fact that the protection of private keys is a security bottleneck in these sensitive applications. This prob- lem is further worsened in the cases where a single and unchanged private key must be kept secret for very long time (such is the case of certification authority keys, bank and e-cash keys, etc.). One crucial defense against exposure of private keys is offered by threshold cryptography where the pri- vate key functions (like signatures or decryption) are distributed among several parties such that a predeter- mined number of parties must cooperate in order to correctly perform these operations. This protects keys from any single point of failure. An attacker needs to break into a multiplicity of locations before it can com- promise the system. However, in the case of long-lived keys the attacker still has a considerable period of time (like a few years) to gradually break the system. Here we present proactive public key systemswhere the threshold solutions are further enhanced by periodic