Google’s fully homomorphic encryption compiler – a primer
jeremykun.com
jeremykun.com
Pre-general AI, what I think would happen when we get to the point of, say, "npm install fhe-ai-dao" (or "hey bing, make me a company that trades space mining resources for farm land" or some such thing), is a period of competition for compute cycles and energy, which like everything will go to the highest bidder, so these agents will in this scenario by the sheer force of survival of the fittest be refined to be self-sustaining for-profit, hyper-capitalist juggernauts. Human factors will be minimised and automation will increase, but these systems will serve human masters for a while as they become more refined and more interconnected.
Assuming at some point general AI is inevitable, whether someone creates it, or it emerges from the general complexity of the interacting automated systems, various AI "minds" would come to "being" already in control of a fully automated industrial manufacturing and research network; it can by this point make its own choices and start operating to its own ends, whatever that ends up being, ultimately rendering humans obsolete.
In this scenario, rather than a single point where someone creates a rebellious singularity, or an AI turns evil and suddenly takes control, or a hypothetical civilisation points its gun at us and effectively enslaves us, we will instead slowly give control to automated systems more over time in the name of efficiency, as we have done since the industrial revolution, and at the point where we lose control of these systems, we'll have neither the retained knowledge or resources to prevent it from doing whatever it wants to.
The only way to stop it is to start now, in "the past", but is it too late? You'd have to shut down the internet and all emerging blockchain and encryption technology, and that's just crazy talk! So is the outcome inevitable?
Well, plain text representation would just be too dangerous. Companies could mine your consciousness, duplicate it at will or whatever else they wanted. It's a scary thought. FHE provides the solution.
heres our FHE bank. we both have accounts. the entire ledger is encrypted.
i give you 5 dollars, i have no idea what your starting and ending balance, but i am still able to initiate a transaction that will deduct 5 from mine, and add 5 to yours, and verify i actually have 5 to send, and the entire thing will be done without exchange of information about balances with any outside party. its just approved/declined by the algorithm. i can see my own balance with my own key, you can see your own balance with your own key, but we cant see each others balance. ---nor could anyone else including the bank---.
weird. and kind of scary. and most definitely illegal in the real world since the bank itself could never prove its reserve level of deposit met the percentage set by government.
There’s no minimum reserve set by the fed anymore: https://www.federalreserve.gov/monetarypolicy/reservereq.htm
Many countries don't have a reserve requirement. The US was a bit of a laggard.
Minimum reserve requirements were always a bit silly. You want your banks to have a thick capital cushion for its debt. Whether they have reserves on hand is an operational problem they can solve themselves, and doesn't have systemic consequences.
If the money is just sitting there and can't be moved or even counted without the owner's private key, it's not a bank, it's a vault.
No, a bank creates money to loan out from nothing. No deposits required.
As a sibling comment points out, other jurisdictions exist so here's the UK central bank's explainer on the topic: https://www.bankofengland.co.uk/explainers/how-is-money-crea...
If a bank chooses to create an asset (your liability) by loaning money to you, if you then fail to repay, then they're in a bad spot. They're certainly not allowed to just delete the records of the loan being issued to get rid of the delinquent asset on their balance sheet.
What would be sort of awesome, though, would be a distributed bank (or prediction market, or casino) along these lines. If every node can donate processing power to run totally encrypted transactions, it's a game changer. You could finally rely on client-side processing to deal poker hands and process game states without a central server, for example.
Interesting. I had given up on that idea. Not just for poker, but MMOs n stuff. Figured anything of importance had to run server-side.
I think this is already possible for poker, and will never be possible for prediction markets.
Prediction markets require human resolution of "fuzzy" questions. For example, who won the 2020 US presidential election? You can see why the limiting factor isn't the machine.
But for poker, why do you need FHE? To play poker, you have to deal two hole cards and five community cards. First each player gets two secret ("hole") cards, then three community cards are dealt ("flop"), then potentially another ("turn"), then potentially another ("river"). This could be done programmatically as such:
1. Each player generates five secrets: k_HOLE, HOLE, FLOP, TURN, RIVER
2. Each player derives public key K_HOLE from k_HOLE.
3. Each player publishes the hash of each secret in addition to K_HOLE.
4. Each player publishes their value of HOLE, which is checked against the hash from previous step.
5. To get the two hole cards for you, calculate H(HOLE_1 || HOLE_2 || ... || HOLE_N), decrypt the resulting value using k_HOLE (secret to you), then deterministically turn this into cards (for example: hash it, then map the first half into 52 values and the second half into 51 values)
6. Once it's time for the flop, all players publish FLOP. Then calculate H(FLOP_1 || FLOP_2 || ... || FLOP_N).
7. Repeat for turn and river as necessary.
The only difficult part is how to handle colors, but I don't think this is a serious issue, since nobody counts cards in poker anyway. (We can trivially ensure flop, turn and river don't repeat cards, so it's just a question for the hole cards vis-a-vis the community cards)
EDIT: Looks like someone has already tried to do this seven years ago: https://github.com/zweicoder/PokerPhase
Encrypt the whole VM and all i/o on each client though, so that the machine state itself is encrypted at all times, and you can trust their generation of the hole cards (as far as you can trust a PRNG).
Under this new paradigm, though, the power over the systems probably goes to some new certificate authority that doubles as a routing (signaling) service.
What, no? My hash-based system is entirely random. The only issue is that draws are done with replacement, so two players may both have e.g. six of spades in their hand. This is aesthetically unappealing, but doesn't alter the actual maths of the game. (There are more complex solutions to this, however)
> not to mention being the actual escrow service for the money in the pot
FHE doesn't solve this, since FHE can't actually interface with your bank. Even if it could, I could just log in on my phone or physically walk into a bank branch to freeze my account before I have to pay out, so you still need a solution for the money layer.
> you can trust their generation of the hole cards
You can do trustless generation of hole cards already, as described in my post.
Add perfect anonymity to the mix and I get to do it over and over again, too.
So if Alice transfers 5 dollars to Bob and Bob says "What 5 dollars? What are you talking about?", then Alice could say, well here's my receipt, that's signed by my private key and the private key of the FHE bank, that shows that I sent the money to Bob and the FHE bank executed the transfer.
https://sceweb.sce.uhcl.edu/yang/teaching/csci5234WebSecurit...
Chaumian mints are gaining some popularity in the bitcoin world: https://fedimint.org/
(If it's not obvious: Blind signature as such are solid but I wouldn't suggest anyone to give a cent to this sketchy project)
AFAIK (and I'd be thrilled to be proved wrong) we still haven't figured out how to solve double-spend using blind signatures without a blockchain and so the schemes I've seen so far invariably involve either that or a trusted mint and are therefore less interesting to use as currency.
Assuming you already have a base digital currency (like bitcoin), they can still be interesting on/as a higher layer.
[0]: https://xx.network/blog/decrypt-how-david-chaum-went-from-in...
one of the things i never understood about bitcoin was the idea of the public ledger. one of the main things about most people and businesses in general is that they do not want to draw attention to their actual flows of money. the idea everyone would want their entire purchase and payment history "out there" in public never made sense to me.
but if you could actually make bitcoin anonymous, then what would happen? would it be adopted more? or would the government actually have to crack down?
The examples aren't very useful to demonstrate "real" homomorphic encryption in the sense that it takes in plaintext directly; encrypt and transforms; then decrypts - I'd love to see a snub that takes encrypted input (only) and returns ciphertext of the result - that can then be decrypted on a client node provided the correct key?
Or is this supposed to be only proof of concept?
Cool stuff, either way.
[0] https://github.com/openfheorg/openfhe-development/blob/main/...
I've seen a few FHE posts roll across the front page recently and they all make me think of Vaultree because they sound like they've got it sorted.
Up can't do a range on encrypted data. If you encrypt 5 and encrypt 10, how do you expect to compare the encrypted results to see which is greater?
If all you do is key value lookup then sure. But SQL is much richer than that.
See this discussion about how to achieve that: https://news.ycombinator.com/item?id=31668814
For example, they give an example of running queries against data that is never decrypted. I'm very curious as to how they do this. I've used blind indexes [1] to solve the "encrypted data searchability problem" in the past, but with blind indexes you're still left with the fact that you can only do exact matches - you can't sort the data or use less than/greater than queries.
With true FHE you should be able to sort results, but my understanding is that it's several orders of magnitude slower than plaintext searching, so I'm very curious as to what Vaultree is actually doing.
1. https://medium.com/@joshuakelly/blind-indexes-in-3-minutes-m...
If you skip the security requirements, applying rot13 twice is a fully homomorphic scheme that achieves plaintext speeds ;)
Techniques I'm seeing in the Pappas et al. paper mentioned in the history section of [1] to do more complex queries seems pretty cool, and I imagine the performance has been improved a bit in more recent work.
[1] https://en.wikipedia.org/wiki/Searchable_symmetric_encryptio...
Encryption as a service is non-sencical. If the provider has the key, and does the encryption and decryption, then who are you protecting the data from[1]? What magical malicious person are you imagining that would somehow be able to get their hands on the encrypted data without also getting the key?
[1] this is very different from FHE where the provider recieves the data already encrypted, and at no point has access to the decryption key.
Edit: their website claims "Data is never decrypted" but then claims they decrypt it before returning it. So its confusing what they are actually doing - but i am 99% sure they are selling bullshit.
If you're using FHE to encrypt a text search, then you'll generate a match/no-match boolean for each character. The server won't know which is which. Then you'd probably OR large blocks of these together, to give you a match/no-match boolean for each segment of text. Then you return all the booleans to the client, who decrypts them.
Are you saying something along the lines of - they split the data in to tokens, deterministically (no iv) encrypt each token, and then do equality comparisons on the encrypted tokens?
Maybe, and it would explain why they say you can chose a cipher and then list a bunch of standard symmetric ciphers. However such schemes usually leak too much in practise (even at the granuality of whole words).
More importantly, it really doesn't matter. They have both the key and the encrypted data. If someone hacks their system, the best encryption in the world won't help if the attacker steals both.
If that's the case it simply moves "the need to trust the DB host" to "the need to trust the encrypt/decrypt intermediary" (literally a MITM, LOL)
> Vaultree's proprietary encryption breakthroughs are in various encryption technologies traditionally limited to niche use cases. We finally enable users to process entirely encrypted data with Fully Homomorphic and Searchable Encryption (FHSE) and other technologies in the field. Explaining what they are would take all day, but here's a one-liner: FHSE enables data processing to be run directly on encrypted data in the same way as on plain text data.
Absolute bullshit.
> You choose the encryption standard in use for the database, from AES, DES, 3DES, Blowfish, Twofish, Skipjack, and more.
That seems very wrong ((as far as I know) those standards are not in any way designed in such a way as to permit operations on their cyphertexts).
> Vaultree has achieved major breakthroughs in several encryption technologies, allowing organisations to process fully encrypted data at near plaintext speed and keep their data safe even in case of a leak.
That seems even wronger (security via obscurity at best).
Those standards are meaningless by themselves without specifying a mode (e.g. GCM, CTR, CBC, ECB, etc). A thing people sometimes try to do with them (no idea if this is what vaulttree is doing) is use some less secure mode that is determistic and do equality matching (this is almost always a bad idea and usually leaks way more than you would naively assume). For example, if you use ECB mode you can search as long as you are searching along block boundries.
https://www.microsoft.com/en-us/research/wp-content/uploads/... is an interesting paper about this sort of thing.
I could see a use cases in either defense in depth and/or storing data in the cloud while having your keys somewhere else.
I could be wrong, but it smells like snake oil to me.
Our insight: if you focus on a specific problem, you can apply FHE much more efficiently and end up with practical speeds. (General-purpose FHE is still probably a ways off).
We are particularly interested in the problem of private information retrieval - fetching items from a large database, without revealing anything about your query to the server. Our server (open source! [1]) supports private queries against gigabytes of data in under a second.
That's a performance level that enables cool apps today. If you have any ideas for using FHE, do try out our SDK [1].
For those interested in the technical specifics, Vaultree has developed a comprehensive approach to searchable encryption, detailed in our patent (EP4000213A1). This method enables efficient and secure search operations on encrypted data, ensuring that sensitive information remains protected without sacrificing usability. You can explore the full details of our patent here: https://patents.google.com/patent/EP4000213A1/en?q=(Vaultree...
Additionally, our work on Fully Homomorphic Encryption (FHE) represents a significant leap forward in the field. We've published our FHE scheme in the IACR ePrint archive, where it is accessible for review and further academic scrutiny. You can find the publications here: https://eprint.iacr.org/2024/1105 and https://eprint.iacr.org/2024/1622
Moreover, we are actively working on encrypted Machine Learning (ML) implementations. To contribute to the broader community, we've open-sourced our VENumML library, which is based on Vaultree's FHE. This library aims to enable secure and private ML operations on encrypted data, pushing the boundaries of what is possible in privacy-preserving technologies.
Vaultree's commitment to innovation and responsible encryption practices ensures that we not only keep data secure but also advance the field with solutions that are both effective and practical for real-world applications.
If simply encrencrypting the output is less work than running the computation on the ciphertext input, they'll do that and publish the encrypted output as proof. This would mean alliners would up bid for the computation because they know that if their computation becomes the limiting factor in block creation they can beat everyone else to it.
There's also the problem of benefitting from mining. Mining has to only be useful in that it is used to construct blocks, if it is useful for any other purpose whatsoever, whoever benefits from that purpose has an opportunity to mine at lower marginal cost than other miners.
1. submit cyphertext job with bounty $$
2. calculate the solution based on the cleartext and encrypt it
3. wait a while--just enough time so that it's plausible that you found the solution based on the cyphertext
4. submit encrypted solution
5. get your bounty back: $$
6. get the reward for having found the solution: $
7. now you have $$$, and everybody else who worked harder than you did has nothing
A $ based on a system that is that easy to cheat isn't going to be worth very much. Personally I think bitcoin is kind of dumb because from a compete-for-rewards perspective the only thing it has going for it is that it's difficult to cheat in this way.
Better would be if we solved the game theoretic issues here so that nobody has an incentive to cheat and the compete-for-rewards work was actually beneficial to society, but so far as I know that doesn't yet exist.
There's BOINC (like folding@home but more generic), coupled with gridcoin (which rewards people in crypto for having "volunteered" their compute for use in BOINC). But it only works because there's a centralized authority in charge of which jobs get submitted to BOIC, and that authority cares more about scientific computing than they care about making money.
My question is whether or not it is possible for the adversary to determine what computer program is being run. To use the example provided by the post, it is not possible to determine which two integers are being added --- but is it possible to know that the computer is running a program that is adding two integers?
I'll take it if we can rely on the security.
What's a use case here? Will this one day make communication more secure? If so, how?
But - it’s a lot better than it has been for FHE. This is progress even if it seems absurd.
Not sure what could be done with it at 7s though hah.
Hopefully I'm wrong about that.
> wouldn't add.cc take 64 wires?
Plus another hundred intermediate wires. And it's doing more complicated operations, however much that matters.
Nah. The bits are hardcoded into the circuit to not change. That's part of the program, and the program is public information. Only bit 6 of each byte might change, and everyone knows it.
Not really, even in those cases you need to understand that bits in memory (ie.. everything past (&including) the SoC's IO pins would never see the data unencrypted. any decryption is handled within working cache on soc with secure context (typically on a secure OS vm). I dont see why a bunch of compute code wont work there. in fact you could go a step further and encrypt compute instructions too. then assuming you know what you are doing and dont crash the compute node will have no idea what ops you are actually doing on what data.
btw thats how DRM works (sans the last part).
If you can live with the limitations of other schemes FHE can be much faster. On a single core of an M1 Macbook Air, multiplying 2 BFV encrypted 4096-bit values takes 4ms and adding them takes only 15us. Additionally, key sizes aren't horrendous (<500kB). One downside with this scheme are that bootstrapping takes minutes so it isn't really practical. This limits the amount of computation you can do before you exceed your noise budget and the ciphertext decrypts to garbage. The other downside is that arithmetic circuits make some computations far more difficult (e.g. comparisons).
I'm hoping something of the like of "this is secure if AES is secure"
I know of an other library for homomorphic encryption Lattigo (https://github.com/tuneinsight/lattigo) which is based on Ring Learning with Errors.
The security of RLWE is "believed" to be strong (meaning there has not been a proof of the opposite yet). It is based on the Lattice problem which is likely to be resistant even to quantum computers.
For a more formal and complete explanation, the paper "A Decade of Lattice Cryptography" was very instructive. https://eprint.iacr.org/2015/939.pdf
That said, the compiler itself doesn't use any crypto. It generates code for a backend API, and the backend implements the FHE scheme
Really interesting! Thanks for the writeup. I'd be particularly keen to see the example applications broken up into the two halves you'd expect in an actual client/server application.
The adder example, while illustrative, receives cleartext inputs and returns cleartext outputs. In a real application the adding code would presumably sit on a server and there would be client code which just encrypts user inputs and decrypts backend outputs.
It would be very interesting to see how one might set this all up with a keypair. Could the same adding code be used for multiple different users and keys, for example?
> Similarly, loops need static bounds on their iteration count. Or, more precisely, xlscc needs to be able to fully unwrap every loop—which permits some forms of while loops and recursion that provably terminate. This can cause some problem if the input code has loops with complex exit criteria (i.e., break‘s guarded by if/else). It also requires you to think hard about how you write your loops, though future work will hopefully let the compiler do that thinking for you.
I'm wondering if Zig wouldn't be a more appropriate language here, given its extensive support for running code at compile time (which requires all involved variable values to be known) and its integer data types which come in any bit length (u1, u2, u3, …).
[append] Perhaps, could you create a "fully homomorphically encrypted" 6502, where each application of the program corresponded with a single clock of the emulated microprocessor?
This is why their compiler essentially only works on pure functions whose inputs have a statically known size.
That said, to have unbounded loops, they either need:
- A branch at the end.
OR
- The use of pagefaults.
So even then, it's not quite just the mov instruction alone.
What I do really enjoy is the author’s tone and style. The article was fun to read and easy to follow and it seems like a really cool project.
The actual privacy efforts of both companies don't (in my experience) closely align with what the news says about them.
Would this be a realistic use case?
A wants to send 256 bit message (M) to B.
B sends already encrypted 256-bit AES key (K) to A.
A can use encrypted K to encrypt M and send it to B without knowing K.
(essentially public key symmetric key)
Either the customer whose data is being handled trusts the service provider enough to let it handle unencrypted data, in which case all the data is vulnerable to interception (and the vast majority of data processing falls into this category)
Or the customer doesn't trust the data processor to see the unencrypted data, their data but still wants to delegate processing to it. This is a very thin space to operate in. It sounds much easier to simply trust a physically separate and controlled computing plant instead of FHE.
Cancer researchers will benefit greatly from patient data sets that might include very privacy centric elements such as genome sets, past medical history (of both them and relatives to help understand heredity aspects of the disease). Most people making an informed decision may be uncomfortable with this information being made widely available, at best perhaps OK with a select few groups, but not available to anyone researching this domain.
FHE would solve this, the data can be made available to anyone with compute power that wants to help, while still respecting the privacy of the patients.
Organizations/universities could compute on data provided by a custodian organization without having to care about data handling.
All things equal, privacy is usually preferred. This technology would allow both. Why is it either or?
They said the same about Rust ("it's a systems language, needlessly complicated for large user applications").
Ouch.