Coinbase Logo

Preventing loss of crypto assets with publicly-verifiable encryption and backup

By Yehuda Lindell

Product

, March 8, 2023

coinbase_cbc_advanced_1600x836px_2MB.gif

One of the major challenges in managing crypto assets is backup. There is a huge focus on security and preventing the theft of assets, but the risk of accidental loss is very real and just as painful. At first sight, backup seems to be quite easy – store the private signing keys in a highly reliable and redundant disaster recovery system! However, a naive implementation of this is risky, since anyone who can access the backup could steal all of the keys and thus all of the assets. The solution is to therefore first encrypt the signing keys and store only the protected ciphertexts in the disaster recovery system. In addition, the private decryption key needs to be protected as well, but this is a single small piece of data, and so is more easily solved. (For example, the key could be on multiple YubiHSMs in diverse physical secured locations.) 

This methodology opens up a brand new problem – the organization responsible for managing the disaster recovery system has no way at all of knowing that the backup is actually valid. Every time a key is generated, a new ciphertext is received and stored. But how do we know that the correct private key is what was encrypted? By definition, encryption hides the plaintext and therefore the ability to determine what’s actually inside! The risk of error may be small, but since the potential loss can be huge, it can’t be ignored. When MPC is used for protecting the keys in the system, then this problem becomes much more acute. In this case, keys are generated between multiple parties and never recombined, with the security property being that even if some of the parties are corrupted and attacking the others, they cannot learn anything about the key. Stated differently, MPC-based systems are robust enough to guarantee security even if some of the participating machines are breached and corrupted. When a key is generated using MPC, each party has a share of the key, and will backup their share – the combination of all of these backups enables disaster recovery of the key. However, once we are considering the possibility of breached machines – or at least we want to ensure security even if this happens – then we also have to consider the possibility that at key generation a machine is corrupted and writes garbage to the backup. In order to achieve the highest level of security, we have to make sure that a corrupted machine encrypts the correct value only. But once again, how can we check this since encryption hides the plaintext value by definition!

One solution is to decrypt and check each backup ciphertext, but this is extremely risky since it unnecessarily exposes highly valuable keys. As a result, some organizations just don’t check and “hope for the best”, or check only a small sample of the encrypted keys – exposing their customers to risk in the event that some of the backup may be corrupted. (It’s important to stress that although this is indeed a low probability event, the expected loss may still be high when dealing with potentially massive losses.)  In this post, we show how it is possible to cryptographically verify the validity of encrypted backup, without revealing anything about the private key, and without decrypting. This method enables the disaster recovery system to verify all backups, and removes the risk of undetected corrupted backup. (Note that from here on, we will talk about backup of a “full” private key. When MPC is used, each backup is actually of a share of the key, but exactly the same methodology works for that case as well.)

Publicly-Verifiable Encryption for Elliptic Curve Private Keys

backup section 2

Constructing Publicly-Verifiable Encryption

backup section 3

Summary – Backup

Now that we have a method for publicly verifying that a ciphertext encrypts the correct elliptic curve secret, we can use it to solve our problem of publicly-verifiable backup. Specifically, each private key is backed up by encrypting it and providing a proof that it correctly encrypts the private key associated with the given public key. Then, a public key is “enabled” for use only after the backup or disaster recovery system has verified that it has a valid backup, and has stored it. This completely solves the paradoxical problem that protecting the private keys requires them to never be opened, but not knowing what is actually encrypted runs the risk of the backups being corrupted. This method is so powerful that the disaster recovery system doesn’t need to have access to the backup decryption key at all, and yet can still be certain that the backups are all valid. There is no need to rely on random sampling or to risk opening private keys at any time whatsoever.

We can even further enhance the backup solution by secret sharing the private key (e.g., into 5 pieces so that any 3 of the 5 suffice to reconstruct the key) and separately encrypting each piece under a different backup key belonging to a different “backup entity”. It is still possible to publicly verify that the 5 ciphertexts constitute a valid 3-of-5 secret sharing of the private key, but now no single backup entity is able itself to decrypt. 

This deployment of zero-knowledge proofs enables us to significantly reduce the risk of theft and loss of crypto asset key backup. This is just one example of where Coinbase deploys advanced cryptography in order to ensure that customers’ funds are safe from theft and loss, taking even very small probability events seriously.

Coinbase logo
Yehuda Lindell

About Yehuda Lindell

Yehuda Lindell leads the cryptography team at Coinbase and is a professor of Computer Science at Bar-Ilan University (on leave). At Coinbase, Yehuda is responsible for the company’s cryptography design and its strategy around secure multiparty computation (MPC). Yehuda obtained his PhD from the Weizmann Institute of Science in 2002 and spent two years at the IBM T.J. Watson research lab as a postdoctoral fellow in the cryptography research group. Yehuda has carried out extensive research in cryptography, published over 100 scientific articles, and co-authored one of the most widely used textbooks on modern cryptography. Prior to joining Coinbase, Yehuda was the co-founder and CEO of Unbound Security, a company that provided key management and protection solutions based on MPC. Unbound was acquired by Coinbase at the end of 2021.