arkana
WTF is Verifiable Encryption
A short exploration on the intersection of privacy and auditability, and the ideas and techniques we use to reconcile them.
A couple months ago, a critical bug was found while auditing the Zcash protocol.
Without going into much detail, the bug happened around the system that validates private transactions in Zcash. The exploit could be used to generate unlimited, undetectable ZEC (the network's native token). To make matters even worse, this was not something introduced in the latest updates, and in fact, the bug had been sitting there for around 4 years, waiting to be found!
As you'd expect, this caused a lot of stir in the blockchain community, to say the least. ZEC prices plummeted, dropping by about 50% overnight. And while a patch came pretty fast, the damage had already been done, and a moderate degree of paranoia had set in.
You see, the entire point of Zcash lies in its privacy guarantees. However, the very system that was supposed to enforce correctness (or soundness, really, if you'll allow me the technicality) had a huge gap in it, and because everything is hidden, there's just no way to tell from the outside whether anyone abused this bug.
In short:
Privacy on its own breaks auditability
And if we look at the bigger picture, this cuts much deeper than just this particular incident. Many systems out there try to provide similar privacy guarantees, while ensuring everything is still correct.
I think it's not an overstatement to say that there's a fundamental tension in any system that combines encrypted information with provable correctness. And this got me thinking: isn't there like a correct solution for this problem? Or a workaround, at least?
My initial instinct was maybe something like "ring encryption", basing myself on the idea of ring signatures, where a member of a group is able to sign anonymously. I thought that maybe you could encrypt things such that both your keys and someone else's (another party like an auditor) would be able to decrypt, and that would be the end of the story.
Turns out this led me down into a pretty interesting rabbit hole, where I learned that not only did I have the wrong name in mind, but also the wrong mental model. My instinct was correct in one aspect though, which is that I was asking myself the right question: can two independent parties both have provable, legitimate access to the same encrypted value?
This happens to be an old question in applied cryptography! And today, I want to give you a glimpse into my explorations on this topic, and show you what some of the most modern systems have to say about this problem.
Shall we?
The Naive Solution
Besides my "ring encryption" idea from before (more on that later), the first instinct most people have is something along the lines of just encrypting the data twice.
More concretely, the idea is to generate a random encryption key (usually called a Data Encryption Key, or DEK) to encrypt the data, and then encrypt that DEK under multiple recipients. Here's a diagram to help visualize the process:
In a way, it's like putting the same key into different envelopes, each addressed to a different recipient. Then each recipient only has to open the envelope by decrypting the DEK, and then use it to recover the original data.
So if we want an auditor to have access to the encrypted information, we simply give them a copy of the DEK they can use!
This is usually referred to as envelope encryption (I know, shocking!). It's a very simple construction, yet it's powerful enough to be the backbone of tools like AWS KMS, GCP KMS, and many key management systems out there.
So there we go! Encryption for multiple parties. Done and dusted!
Come on, it'd be no fun if the article just ended there, right?
Well, not quite. You see, envelope encryption works wonderfully, but only as long as two conditions hold.
The first condition is one of the most central aspects to all of cryptography: trust. Because if you think about it, a third party can never trust that the DEK in the envelope actually matches the one used to encrypt the data in the first place!
I know it sounds weird, but the whole point of having an auditor is that they don't necessarily trust you. Whoever creates the DEK envelope (be it you, or another party) could have carefully crafted a DEK that recovers a tampered version of the original data, and the auditor would have no way to tell!
What makes it even worse is that a DEK is usually just a symmetric key: a bare secret, with no public fingerprint tying it to the ciphertext it supposedly produced. There's simply nothing for the auditor to check against.
So before we hand out even a single envelope, we already have a problem on our hands: nothing ties the key inside it to the data it's supposed to open.
This is a live concern in production, not just a hypothetical. For example, Aleo's transaction view keys get their hash committed on-chain, so the key itself can later be authenticated. But notice what that does and doesn't buy you: it proves you got the real key, not that the key opens onto an untampered value. Without further guarantees, the gap remains.
Even then... that's still the easy part! Remember, there's still the second condition that needs to hold.
And that's where things start getting a little more spicy.
Where Things Begin to Break
Let's assume we somehow manage to prove the DEK is correct (and there are indeed some ways to go about this), so we can put the trust issues to the side.
In that case, envelope encryption works fine... as long as the data itself remains unchanged.
How so, you may ask? Picture for example a private blockchain, much like Zcash. Naturally, the balances here are encrypted (I mean, again, that's the whole point). But you know what's also true about balances? Bingo: they change over time! When you receive a payment or when you spend your tokens, your balance will be modified. And the network needs to perform those updates, without ever decrypting anything.
Yup. Read that again. It's a weird requirement indeed:
The system needs to do arithmetic on numbers it isn't allowed to see
But how the heck would that work? Sure, with envelope encryption, adding two numbers together would be as simple as decrypting the two values first, but the moment we do that, privacy goes poof!
What we need to solve this problem is a special kind of encryption, where the math can be performed on encrypted data. Weird as it may sound, I promise it's possible - and if you've been following my blog along, you know full well where this is headed: we're gonna need the power of homomorphisms!
A Primer on Homomorphic Encryption
Homomorphic encryption is an interesting and deep topic, so for the purposes of this article, I'm gonna have to keep it brief. I reckon a little primer should do the trick for us today though.
And if you want to, you can read more about this topic here and here.
In a nutshell, some encryption schemes let you operate on ciphertexts directly, in such a way that the order of the operation and encryption can be interchanged. Something like:
Mind you, this isn't some crazy property to find. Schemes you may already know or have heard of, like ElGamal and Pedersen commitments, are additively homomorphic out of the box.
And notice, this property is exactly what we need for our private blockchain scenario: the system can just operate on the encrypted data, without really knowing whatever the heck the result means, and the owner of the balance can decrypt later. Wonderful!
Having said that, the next step seems rather obvious: how about we try to make our envelope encryption homomorphic? You know, encrypt the data in such a way that arithmetic continues to (sort of magically) work.
Yeah, it's a good instinct, except envelope encryption breaks completely when we try this, for the simple reason that it's not built for this.
In short, it breaks because of the kind of keys our envelope strategy relies on: symmetric keys. The point of using symmetric keys is to allow anyone to decrypt, as long as we can send them an envelope. And symmetric ciphers like AES are specifically designed to scramble their input into something that looks like random noise, without much of a usable relationship between one ciphertext and another. That's what makes it secure, and it's also what makes it absolutely not homomorphic: you simply can't add two AES ciphertexts and expect to get any meaningful result.
In fact, homomorphisms need ciphertexts that live in a rich algebraic structure you can do arithmetic in. What we're saying is that symmetric ciphers throw that structure away on purpose.
Conversely, the homomorphic schemes you'll find out there are all asymmetric (or public key) schemes!
In that case, let's ditch envelope encryption! What if we choose to encrypt the balance under a public key, out in the open? This way, the network can operate on it homomorphically while only the key's owner can decrypt.
Surely that's enough, right? ...Right?
Oh, I wish it were!
Matching the Data
Okay, let's gather our progress real quick before continuing.
With homomorphic encryption techniques, we're now able to operate on ciphertexts. This is no small feat, but it's not our only goal.
Remember, we still need to encrypt in such a way that both the owner of the data (like a balance) and some auditor can both decrypt. Envelope encryption handled that gracefully, but struggled with arithmetic. So what happens with our new toy now?
Well... in its standard form, homomorphic encryption is designed to operate on ciphertexts encrypted under the same key. Yup.
This is a perfect time to go back to my original hunch, that "ring encryption" stuff I mentioned earlier. My idea was that both parties belonged to a group, and shared a secret key that we could encrypt to.
The idea was partially right, with the "ring" part not being correct. Ring signatures are used to ensure anonymity inside a group of possible signers, which is something we don't really care for in this case. But the part where we encrypt for a shared key... that bit does make sense, as we'll discuss a little further ahead!
So in order to get an auditor to decrypt the data, we essentially need to encrypt the same data twice: once under the owner's public key, and another one under the auditor's public key. And that introduces yet another problem: how do we know both ciphertexts map to the same unencrypted data?
I know, I know... it seems we're running in circles.
For your peace of mind, I'll say that everything was building up to this very moment.
We no longer have problems with the arithmetic side of things, so there's this single remaining problem we need to solve. Ideally, what we need is a way to prove that two ciphertexts encrypt the same value.
And when I say prove, I mean mathematically prove.
Turns out cryptographers have been chewing on exactly this problem since the early '90s. It even has a name, and a very on-the-nose one at that.
Verifiable Encryption
Regardless of our motivations so far, there's something that's always true for encryption: it's meant to hide the encrypted information! Therefore, we can never check anything about the original data (or plaintext) directly without decrypting.
Instead, verifiable encryption takes a different approach. And it may even feel quite natural once we put it into words:
Attach a mathematical proof that two ciphertexts hide the same value, without revealing what that value is
That proof works exactly like a receipt: you get the ciphertext (which you cannot read), plus something that certifies that the original plaintext is "correct" in some sense. Once you verify the receipt, there's no need to trust the ciphertext any longer, and you can just move forward. And in our case, "correct" means one very specific thing: that two ciphertexts hide the same value!
More generally, that "receipt" can certify any condition about the plaintext, not just equality. But we'll stick with equality, because it's exactly the flavor we need right now.
Awesome! Combined with homomorphic arithmetic, we can now build systems that can operate on ciphertexts, and allow third parties to check results via a little proof.
All that remains is to understand how this is done mathematically.
Building the Proof
The tool for the job is a sigma protocol: a compact little exchange where a prover convinces a verifier that two ciphertexts share the same secret, without ever revealing the original value.
If you want to learn more about these, check this article out!
We could take it a step further, since sigma protocols are really just one family of dedicated zero-knowledge proofs.
In our case, we're looking to prove that two ciphertexts map to the same data, for which there's the classic Chaum-Pedersen protocol, dating back to 1992. Later attempts sharpened this into more practical schemes, like the ones proposed by Camenisch-Damgård or Camenisch-Shoup.
But since we've stepped into ZK territory... Do we have to restrict ourselves to proving particular things about ciphertexts? Could we not prove arbitrary stuff about the encrypted data? Or even:
What if verifiable encryption was a ZK problem all along?
Oh yeah.
There are some nuances around this (which I don't think I have the luxury to cover in this piece), but the core idea remains: we can talk about certified ciphertexts, and stop thinking about proving stuff about one balance.
A certified ciphertext is just a ciphertext with a receipt stapled to it, proving that whoever created it actually knows the plaintext, and that it satisfies whatever rules the system demands.
In essence, the proof is just a statement about hidden data. Once we adopt that mindset, equality proofs become just one kind of statement we can prove, and we can start thinking about arbitrary confidential computations over encrypted values (and arbitrary checks on said computations). This is what the guys at Zama are pursuing: by combining (fully) homomorphic encryption and ZK proofs, the network can process encrypted data while keeping things verifiable through and through! Aleo leans on the certified-ciphertext half of that same idea, minus the homomorphic computation: every private transaction is computed off-chain by whoever holds the plaintext, then submitted as an encrypted record with a zk-SNARK proof that the hidden data obeys the program's rules — checked on-chain without ever being decrypted there.
Limitations
It sounds amazing (and by any reasonable measure, it is), and almost too good to be true.
And you know how these things go by now.
So let me ask you a seemingly innocent question: if the whole network is happily computing on everyone's encrypted data, then... whose key is it all encrypted under?
Think about it for a second. It can't be your personal key, and mine, and everyone else's, all at once, since the network would be staring at a pile of ciphertexts under a hundred different keys, with no way to add your balance to mine. For the homomorphic magic to work across everybody's data, there needs to be one key the whole system encrypts under. A single, global encryption key.
Remember that "shared key" idea from before? Yeah, my mental model was wrong, but that one detail was reaching for exactly this: it's not a ring we need, but a shared key the whole group encrypts to.
That seems to solve our problem... except a global key is a bit of a terrifying object. Because now the obvious question becomes: who holds it?
Whoever holds that key can decrypt everything. Everything becomes transparent to them. It's a lot of power to hand to any single party. Can we trust anyone?
Of course, the answer is no. And the natural fix is to not let anyone hold it, but to split it across a committee, threshold-style, so it takes a quorum to decrypt anything.
That's almost the perfect solution, but it has a last caveat. Look closely at what it quietly implies, because this is where things get spicy again:
The committee can always decrypt your data. And you can't decrypt it without them
Who Owns the Data?
That single sentence actually hides two different problems, and it's worth piecing them apart, because they don't have the same answer.
The first one is: the committee can read your data without you. Uncomfortable, sure, but as it turns out, it's relatively easy to close this gap. We simply add you to the group of parties required to decrypt, so that nothing can be opened unless you and the committee agree. A small tweak to the access structure, and now nobody reads your data behind your back.
We've turned the rule into an : committee and user. Not too bad!
Except... this cuts both ways! Since decryption now needs your cooperation too, you also gain a veto over any audit aimed at you. If the whole point of the committee was to investigate misbehavior, and the whole point of misbehaving is not cooperating, this "fix" has the potential to undo the auditability we set out to preserve! As they say, there's no free lunch.
The second problem is the nastier one: you can't recover your data without the committee. Picture the committee going offline, or simply refusing to cooperate. Suddenly, your funds, your balance, your everything, are locked away forever, and there isn't much you can do about it.
To fix this problem, we'd want the opposite rule: let either you or the committee decrypt on their own. An instead of an .
So how do we build an ""? Luckily, there's no need for any fancy cryptography here, and we can just reuse an idea from a few paragraphs before: we just encrypt the value twice! Once for you, and once for the committee.
Two independent ciphertexts for two independent keys, and of course, some way to guarantee they both hide the same value.
In sum:
Two parties, two keys, provably the same secret, and no trust in-between
And that finally solves our problem, and we can set our minds at ease. Auditability and self-custody, both achievable at the same time. It's not perfect (we need to track two ciphertexts rather than a single one), but we get everything we need.
Neat, eh?
Summary
So there you go! That's verifiable encryption.
It was not an easy path to traverse, I reckon. So let's retrace our steps real quick and round this whole mess up.
Everything started with us wanting two parties to share access to encrypted data, and reached for the naive fix: envelope encryption, one key sealed into many envelopes.
It works, until we ask the data to change while encrypted, which sends us to homomorphic encryption. But homomorphism only lives under a single key, so sharing access means encrypting twice, which drags in the real monster: how do we know both ciphertexts hide the same value?
That question is what verifiable encryption answers. It's an old idea powered by sigma protocols and, more recently, general zero-knowledge proofs, which let us build all the way up to certified ciphertexts and fully confidential computation.
Then, right at the end, we chased something that looked unrelated at first (getting your own data back from a threshold committee), and bumped right into the same problem verifiable encryption solved in the beginning: proving that two ciphertexts hold the same value.
Scratch the surface of almost any system that mixes privacy with provable correctness, and you'll find the same quiet question time and time again:
Can two parties hold the same secret, and prove it, with no trust involved?
Which, if you think about it, is exactly the tension I mentioned back in the very beginning. Privacy on its own breaks auditability, yes. But it doesn't have to. We just need the right tool to put the two back together.
And now you know how to call it.
See you on the next one!
Did you find this content useful?
Support Frank Mangone by sending a coffee. All proceeds go directly to the author.