Recovering Encrypted Data Without Your Decryption Key

Private cloud backups are a vital tool in today’s digital landscape. Backups, in general, allow users to store important information off-site on a server, ensuring that the information remains available even in the event of a local failure. Adding privacy measures allows users to back up sensitive information, such as the key to their cryptocurrency wallet. This addition introduces a tradeoff between privacy and availability.

Privacy requires remembering some cryptographic secrets, like the decryption key and digital signature key, or a password, without which the user loses their availability. A recent work coauthored by a member of our research team [1] explores the interesting question of whether this tradeoff can be avoided.

More specifically, can a user recover encrypted data stored on a cloud server even when they do not remember anything?

The Problem

Suppose that Alice wants to back up her cryptocurrency wallet key on a remote server in order to retain availability if her local storage fails. Alice must store her wallet key privately: if it is revealed to any other party, that party will have access to her funds. Further, suppose that after Alice has stored her wallet key, she has somehow lost all means of accessing that backup: any cryptographic keys that she used to perform the storage, access to her personal devices, she even forgot any passwords that she had used to set up the backup. While it seems that Alice’s key is now lost forever, [1] shows that if the proper steps were taken during storage, she can still recover her key.

This problem can be broken down into two subproblems: credential-less authentication, and emergency recovery. In credential-less authentication, Alice must prove her identity to the server storing her wallet key. She must do this while remembering nothing, making digital signatures or password-based authentication unusable in this setting. Further, we must ensure that Alice is the only one who is able to authenticate, otherwise an adversary could come and steal Alice’s wallet key.

In emergency recovery, Alice must break the confidentiality of the stored information. Because Alice wants her wallet key to remain private throughout storage, she uses a cryptographic technique to hide the true value from the server. This is most often done through encryption, where Alice encrypts her wallet key, using an encryption key unknown to the remote server, and sends the subsequent ciphertext to the server. By the security of encryption, we know that the server learns nothing about the wallet key from the ciphertext. However, in an emergency recovery, Alice has forgotten her encryption key. This means that she also learns nothing about her wallet key from the ciphertext. Alice, therefore, needs a way to break the encryption. Further, we must ensure that only Alice can break the encryption, else an adversary could steal her wallet key. Encryption could be avoided altogether if Alice hires multiple servers and secret-shares her wallet key. Secret sharing is a primitive where Alice splits her wallet key into pieces such that given enough pieces, one can reconstruct the original value. A simple example would be choosing n numbers that sum to Alice’s wallet key. Then, one of these pieces is sent to each of the employed servers. This approach, however, requires Alice to trust some subset of the employed servers, which we wish to avoid, because if all servers misbehave, they could collaborate to steal her secret without her knowledge.

This leaves us with two questions to answer:

1. How can only Alice prove that she is Alice, even when she has forgotten everything?
2. Given that Alice has proven her identity, how can only Alice break the security of encryption?

Credential-less Authentication

Credential-less authentication is the process by which Alice, and only Alice, can prove her identity. Suppose that Alice is a member of a group of people who all start with some form of credential, like an ID card. When all parties possess their IDs, authentication is easy: Alice simply presents her ID. But how can Alice prove her identity when she has lost her ID? She can simply reclaim her identity by announcing that she is Alice. Alice announces to the group that she has lost her ID card, but that she is indeed Alice. Surely, if this were not Alice, the real Alice would refute the claim by presenting her own ID. This shows how Alice can stop an adversary, say Eve, from stealing her identity. If Eve claims to be Alice, then Alice can prove that this is a malicious request by presenting her own ID. Note however, that when Alice has lost her own ID, she must make this announcement immediately, as she has also lost her ability to stop Eve from stealing her identity.

The protocol presented in [1] uses a permissionless blockchain to make this announcement, and digital signatures in the place of an ID card. Alice registers with a particular server in the authentication protocol by announcing the server’s digital signature verification key and her digital signature verification key on chain, establishing her identity. Later on, when Alice has forgotten everything, she posts a request on chain, potentially from a new account, claiming to be Alice. If no party posts a signature from Alice denying this claim, then it must have been Alice making the request. If it was Eve making the request, then Alice simply posts a signature denying the request. Of course, we cannot wait forever for a denial to be posted, so Alice must decide upon registration how long she will give herself to respond to a request, in [1] this is referred to as the challenge time, t(chal). Then, the block containing her request and the t(chal) blocks afterwards serve as proof of Alice’s authentication.

This, however, does not provide Alice with sufficient protection. Eve could employ a front-running attack to steal Alice’s identity. Alice’s request will appear in mempool before it appears on chain, and mempool is publicly available. Meaning that Eve can see the request in mempool, and rush her own post claiming Alice’s identity first. [1] uses a standard technique for mitigating front-running attacks, known as commit-and-reveal. In this approach, Alice first posts a cryptographic commitment to her request. Upon seeing the commitment on chain, Alice can post the opening. To prevent Eve from posting a commitment to a request on Alice’s behalf and front-running her opening, Alice sets a second timing parameter upon registration: open time t(open), which determines how long Alice has to open a commitment to a request. Now, the t(open) blocks before Alice’s request, which must contain a commitment, and the t(chal) blocks afterward her request serve as proof of Alice’s authentication.

But there is one final problem here. Alice must give herself sufficient time to respond to Eve’s malicious requests. Alice cannot be expected to constantly monitor the chain for such requests and respond immediately. Eve may take advantage of personal knowledge about Alice to make a timely request. For example, if Eve knows that Alice is going camping and will be away from her devices for a week, she could make a request during the trip and catch Alice off guard. Alice must therefore give herself weeks or even months to respond to requests made on her behalf. Setting t(chal) to such a lengthy period would result in many blocks being included in the proof of authentication: potentially hundreds of gigabytes of data. If this proof needs to be passed along to another party, as it will be in the emergency recovery protocol, this becomes infeasible. This is solved by having Alice set a third timing parameter upon registration, the waiting time t(wait). This is the amount of time that passes after the request, before a denial can occur. The blocks during this period are not included in the proof of authentication, and therefore has no impact on the size.

Putting this all together, Alice first registers for the credential-less authentication protocol by announcing her server’s and her own digital signature verification keys as well as her three timing parameters t(open), t(wait), and t(chal) on chain. Alice then uses her signing key, as long as she has it, to respond to malicious requests by signing and posting denials. It is vital that Alice not post her denial during the waiting period, since these blocks are not part of the proof. When Alice loses her credentials, she posts her own request. First, posting a commitment to the request followed by an opening to the commitment within time t(open). Then begins the waiting period. Once time t(wait) has passed, the challenge period of time t(chal) begins. Since Alice is the one making the request, she can be certain that no denial will be posted. Her proof of authentication is the t(open) blocks before her request, which must contain a commitment to the request, and the t(chal) blocks occurring t(wait) blocks after the request, which must not contain a denial.

Emergency Recovery

Now that Alice has a method of authenticating herself even after losing her credentials, we need a way for Alice to break the security of encryption. Suppose that Alice has already stored a ciphertext on the remote server, but has forgotten her decryption key. Then, Alice and the remote server are both stuck with a ciphertext that tells them nothing. One way that Alice could break the ciphertext, or rather, have the server break the ciphertext for her, is if the server was able to run a secure “re-encrypt” procedure. What we need from this procedure is that the server decrypts the ciphertext and encrypt the plaintext under a fresh public encryption key chosen by Alice, without ever revealing the plaintext to the server. If the cloud had Alice’s original decryption key, it would be able to perform such a re-encryption, however this would reveal the plaintext to the cloud. Further, the server cannot be in possession of Alice’s decryption key: If the server has Alice’s decryption key, it would be able to steal Alice’s wallet key, because we consider the server to be untrusted. But even if the the server is untrusted, it can still host trusted hardware, such as a Trusted Execution Environment (TEE).

A TEE is a secure hardware enclave within an untrusted host. In this enclave, storage and computation are hidden from the host, despite sharing the same hardware. Further, the output of the TEE comes with an unforgeable attestation, like a digital signature. This allows Alice to ensure that she truly is talking to the TEE instead of the host pretending to be the TEE. Alice can then make use of a TEE hosted by the server to securely decrypt her ciphertext and re-encrypt it under a freshly chosen public key.

All together, this protocol involves Alice performing a key exchange with the TEE via the server to establish a shared symmetric key. Then, Alice encrypts her wallet key under this shared symmetric key, and sends the ciphertext to the cloud, who forwards it to the TEE. Later, when Alice has forgotten her wallet key, her encryption key, and everything else, she authenticates with the credential-less authentication protocol, and passes this authentication token to the cloud, who forwards it to the TEE. If the authentication token verifies, the TEE will perform the re-encryption, and send the fresh ciphertext back to Alice.

There is, however, one last complication. The credential-less authentication protocol we discussed makes use of a permissionless blockchain, and the TEE is simply a hardware enclave, incapable of truly communicating with the outside world, except via their host. This gives the server the ability to forge an authentication token and steal Alice’s secret, falsely claiming that the token comes from the chain. [1] therefore borrows the techniques of [2], using a publicly verifiable ledger. Here, public verifiability means that any party is able to verify that a block truly comes from the chain, even without access to the ledger. Such a verification would likely require some auxiliary information, such as the genesis block of the chain. This auxiliary information would be provided by Alice upon storage. Now, the TEE can ensure that an authentication token truly is valid.

How to Recover a Cryptographic Secret from the Cloud

Figure 1, taken from [1] shows the composition of the two protocols. Alice begins by registering with the cloud server through the credential-less authentication protocol, posting the cloud’s digital signature verification key, her own verification key, and her three timing parameters t(open), t(wait), and t(chal). Once Alice is registered, she engages in a key exchange with the TEE via the cloud to establish a shared symmetric key. This key is used to encrypt Alice’s wallet key, and the ciphertext is sent to the cloud and stored.

Later, when Alice has forgotten everything, she finds her registration transaction to re-learn her timing parameters. She then posts a commitment to a request to recover her stored secret under a fresh public key. Once the commitment has been posted, Alice can open the commitment to her request, making the announcement public. The cloud then waits for the waiting period to pass, which begins the challenge period. The cloud waits for the challenge period to pass, then collects the t(wait) blocks before the opening, and the t(chal) blocks occurring t(wait) blocks after the opening. If there is a signed denial in the challenge period, the cloud does not proceed. If there does not exist a denial in the challenge period, the cloud forwards the authentication token to the TEE.

The TEE also verifies the authentication token, ensuring that the cloud did not cheat. As long as the authentication token verifies, the TEE uses the stored symmetric key, established with Alice via key exchange during storage, to decrypt the stored ciphertext. The TEE then encrypts Alice’s secret using the fresh public key included in her request. This ciphertext is forwarded back to Alice via the cloud.

For more details on how to solve this interesting problem, we recommend the reader check the full paper [1].

References

• [1] David Adei, Chris Orsini, Alessandra Scafuro, and Tanner Verber. How to recover a cryptographic secret from the cloud. In Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS 2025, Taipei, Taiwan, October 13–17, 2025. ACM, 2025.
• [2] Gabriel Kaptchuk, Matthew Green, and Ian Miers. Giving state to the stateless: Augmenting trustworthy computation with ledgers. In 26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24–27, 2019. The Internet Society, 2019.