1. A method for storing information in a recoverable manner on an untrusted system, comprising: sending, by a client, a request to a recovery server for recovery of a failed database; determining whether said request is legitimate; based on said determining, sending an old local key to the client; decrypting by said client the failed database with the old local key, to recover the failed database; and re-encrypting the recovered database with a new local key.