One embodiment of the present invention provides a system that facilitates securely forgetting a secret. During operation, the system obtains a set of secrets which are encrypted with a secret key Si, wherein the set of secrets includes a secret to be forgotten and other secrets which are to be remembered. Next, the system decrypts the secrets to be remembered using Si, and also removes the secret to be forgotten from the set of secrets. The system then obtains a new secret key Si+1, and encrypts the secrets to be remembered using Si+1. Finally, the system forgets Si.