A secure remote-data-storage system stores encrypted data and both plaintext and encrypted keys at a server, where data at the server is inadequate to recover the plaintext of the encrypted data; and stores at least one encrypted key at a client system. To decrypt the data, the client must obtain a copy of the encrypted data from the server, and a key to decrypt its locally-stored encrypted key. Once decrypted, the locally-stored key can be used to decrypt the encrypted data, or to decrypt an encrypted key from the server, which may then be used decrypt the encrypted data.