Verifiable Encryption: Escrowing a Crypto Wallet Key Without Revealing It

Alice keeps her savings in a crypto wallet, and wants a loan from her bank using them as collateral. The bank has a reasonable worry: if Alice loses her private key, the collateral is gone forever, and if Alice disappears, the bank can’t touch it either. So the bank asks Alice to escrow her private key with a trusted third party, sealed, to be opened only if she loses access to her wallet. But how does the bank know that the sealed envelope really contains the right key? Alice could just as well seal a random number, or the key of an empty wallet. The bank can’t open the envelope to check—that’s the whole point of sealing it.

This is the problem verifiable encryption solves. Alice encrypts her private key for the trusted third party, and attaches a proof that the ciphertext contains exactly the private key behind her wallet’s public key. The bank, which knows only the public key, checks the proof and learns nothing else. In this final post of our series on zero-knowledge proofs for homomorphic encryption, we’ll build it with LightPHE in Python, Go, Java and TypeScript.


🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

Cryptography Basiscs From Scratch In Python

What Verifiable Encryption Proves

Three parties take part, and only one of them ever needs a private key:

alice (prover):            knows her wallet's private key x, whose public key is X = x * G
                           encrypts x for the trusted third party, and proves it

bank (verifier):           knows X, e.g. from the blockchain, and the trusted third party's public key
                           checks that the ciphertext contains log_G(X), without learning x

trusted third party:       holds the private key of the encryption
                           decrypts the ciphertext only when the agreed conditions are met

Notice how this differs from the proofs in the previous posts of this series. A proof of knowledge showed that the encryptor knows what’s inside a ciphertext, and a range proof showed that the content is within bounds. Verifiable encryption connects the content of a ciphertext to something that lives in a completely different world: a public key on an elliptic curve. The ciphertext is a number modulo a large RSA-like modulus, while the public key is a point on a curve of a different size, and the proof has to bridge the two.

How It Works: Camenisch-Shoup

LightPHE implements the scheme of Camenisch and Shoup from Practical Verifiable Encryption and Decryption of Discrete Logarithms (CRYPTO 2003). Its encryption lives in the same kind of group as Paillier, with a large plaintext space that easily holds a 256-bit private key, and it adds two ingredients on top:

  • A bridge between the two worlds. The proof commits to the secret under an auxiliary modulus, and shows with Fiat-Shamir that the same number is inside the ciphertext, behind the curve point, and small enough not to wrap around in either world. Its soundness relies on nobody, in particular not the prover, knowing the factorization of that auxiliary modulus, which LightPHE discards right after generating it.
  • A label. Every verifiable ciphertext carries a validity tag computed over a label, a public string chosen by the encryptor, such as “release only if alice loses access to her wallet”. The label is part of the proof, so the bank verifies the escrow together with its conditions. And the trusted third party can decrypt only with exactly the same label: change a single character, and decryption fails. The conditions can’t be swapped after the fact.

The validity tag also makes verifiable ciphertexts non-malleable: nobody can modify one without breaking it, which is what makes the scheme secure against chosen-ciphertext attacks. That’s the opposite of homomorphism, so verifiable ciphertexts reject homomorphic operations, while regular Camenisch-Shoup ciphertexts remain additively homomorphic, just like Paillier’s.

Required Cryptographic Features

1. A large plaintext space with direct decryption, so that a whole private key fits into a single ciphertext and comes back out exactly. Schemes that decrypt by solving a discrete logarithm can’t do this for a 256-bit number.

2. A proof across groups that ties the plaintext of the ciphertext to the discrete logarithm of a point on an elliptic curve, including a check that the secret is small enough not to wrap around.

3. Labels and chosen-ciphertext security, so that the escrow can’t be modified, and its release conditions can’t be changed.

4. Support for the curve of the escrowed key. Bitcoin and Ethereum keys live on secp256k1, which is the default, while many signing keys live on Ed25519. LightPHE takes the curve’s form and name when building the cryptosystem.

Which Algorithms Can Be Used, and Why

Only one cryptosystem in LightPHE offers verifiable encryption, and it was designed for exactly this job. I tried the others, and LightPHE refused each with does not support verifiable encryption:

AlgorithmsVerifiable encryptionWhy
Camenisch-Shoupâś…Large plaintext space with direct decryption, a proof linking the plaintext to a discrete logarithm on a curve, and labeled, non-malleable ciphertexts
Paillier, Damgard-Jurik, Joye-Libert, Bresson-Catalano-Pointcheval❌They have a large plaintext space, but they are malleable by design, with no labels, and LightPHE has no proof linking their plaintexts to curve points
Exponential ElGamal, Elliptic Curve ElGamal❌Their decryption solves a discrete logarithm, so the trusted third party could never get a 256-bit key back out
Damgard-Geisler-Kroigaard❌A 32-bit plaintext space can’t hold a private key

Example 1: Escrowing a Wallet Key

Alice escrows the private key of her wallet on secp256k1 with a trusted third party. The bank verifies the escrow against her wallet’s public key before granting the loan. We also check what happens if Alice tries to escrow a different key, and if the trusted third party tries to release the key under different conditions.

The real escrow verifies, and the decoy doesn’t, even though it is a perfectly valid encryption of a perfectly valid number: it just isn’t the private key behind Alice’s public key. The trusted third party recovers the key with the agreed label, and gets an error with any other. It’s also fast: on my laptop, escrowing took 0.13 seconds and produced a 3 KB escrow, and verifying it took 0.08 seconds, after a one-off key generation of about 1.4 seconds for the trusted third party. Java snippets use assert for brevity, so run them with -ea to enable assertions.

Example 2: An Auditor Checks the Escrows of a Company

A company’s employees sign documents with Ed25519 keys, and the company requires every key to be escrowed with a recovery service, so nothing gets locked away when someone leaves. An auditor checks every escrow against the employees’ public keys, without being able to use a single key. One employee, Bob, mistyped his key while escrowing it.

The auditor flags Bob’s escrow today, while Bob is still around to fix it, instead of the company discovering years later that his key can’t be recovered. The only change for Ed25519 is the curve’s form and name when building the cryptosystem; everything else stays the same. When the public key of the recovery service is loaded from a file, the curve is passed again.





More Scenarios

  • Crypto-backed loans: A bank verifies that a customer’s wallet key is escrowed before accepting the wallet as collateral, without ever seeing the key.
  • Digital inheritance: A wallet owner escrows the key with a lawyer under the label “release to my heirs upon my death”, and the heirs can verify today that the escrow will actually work.
  • Regulated exchanges: A crypto exchange verifies that a customer’s key is escrowed under conditions agreed with a regulator, e.g. release only with a court order, without learning the key itself.
  • Corporate key recovery: A company escrows the encryption and signing keys of its employees with a recovery service, so an auditor can verify that every key is recoverable, while neither the auditor nor the service can use them under normal conditions.

Caveats

  • The trusted third party is still trusted: The label makes sure the trusted third party decrypts the escrow with exactly the agreed conditions written on it, but whether those conditions are actually met in the real world is a human decision. Choose the trusted third party carefully, and log every release.
  • Key generation must be honest: The proof’s soundness relies on nobody knowing the factorization of the auxiliary modulus, which is discarded when the trusted third party generates its keys. A trusted third party that kept it could collude with a prover to pass off fake escrows.
  • Escrows are not for computing: Verifiable ciphertexts reject homomorphic operations to stay non-malleable. Use regular ciphertexts created with encrypt for homomorphic computations.
  • Small keys are refused: The trusted third party’s key must be large enough to hold the curve’s private keys with room for the proof, so LightPHE refuses keys that are too small for verifiable encryption.

Conclusion

Verifiable encryption lets you hand over a sealed secret and prove what’s inside without opening it. With Camenisch-Shoup, Alice escrows her wallet key, the bank checks it against her public key, and only the trusted third party can open it, and only under the conditions written on its label. That takes a large plaintext space, a proof that bridges a ciphertext and an elliptic curve point, and labeled, non-malleable ciphertexts, which is why Camenisch-Shoup is the one cryptosystem in LightPHE built for it.

That wraps up our series on zero-knowledge proofs for homomorphic encryption. We kept the encryptors honest with proofs of knowledge, allowed values and ranges, kept the decryptors honest with proofs of decryption and partial decryption, and now we can even prove that a ciphertext holds the key to a wallet—in a few lines of Python, Go, Java or TypeScript.


Support this blog financially if you do like!

Buy me a coffee      Buy me a coffee


Leave a Reply