12 ms·
Google’s fully homomorphic encryption compiler – a primer
- noman-land 4y ago[flagged]
- deleted 4y ago[deleted]
- 7e 4y agoHow many orders of magnitude slower is this?
- Palomides 4y agoauthor shows a program that adds two integers and takes 7 seconds to run, and the way the system processes data results in 20000x the RAM usage
- willcipriano 4y agoSo similar to your average electron app.
- nevir 4y agoTurns out Electron is SUPER SECURE
- xrd 4y agoThere is something surreal about the last example where you take a Rick Astley video that's 9MB and it becomes 188GB after FHE. That seems like a new category of rick-rolling by some cyberpunk.
- tossaway0 4y agoWe've complained long enough about complexity in code being the barrier to speed. Now it's processing power once again. I'll take it if we can rely on the security.
- barbazoo 4y ago> 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?
- phkahler 4y agoMy bet is on digital currency. Your wallet will be able to send and receive from other wallets locally. Not like crypto. No distributed ledger. You will make transactions locally. You can't just alter your balances though because they are encrypted. Not sure how you get data in or out without keys though. FHE will be a part of such currency though.
- fnordpiglet 4y agoAdding two numbers takes 7 seconds, so many many many But - it’s a lot better than it has been for FHE. This is progress even if it seems absurd.
- flangola7 4y agoIf all you need to do is handle a symmetric key exchange that you then use for everything else, that might be enough.
- sillysaurusx 4y agoThis is tempting to believe, but unfortunately the dream is to be able to run applications on someone else's servers without them knowing what you're doing. That's when I lost interest in FHE. If you want to use it, you have to use it everywhere, and it's just too slow. Hopefully I'm wrong about that.
- TeMPOraL 4y agoI feel it's already at the edge of being useful in practice. Compute and memory are cheap, and we're wasting a lot of it - so even with overhead this big, simple calculations wrapped in FHE wouldn't be prohibitively expensive - and may just be useful enough to create new types of software systems.
- NovemberWhiskey 4y ago7 seconds to add two numbers; that's roughly, what, 10 orders of magnitude slower than without FHE? I'm not sure compute is that cheap.
- unshavedyak 4y agoIt would be interesting to see a whole new generation of writing apps with hyper optimized code. We suddenly go back to the 1950s(?) in relative compute power for apps behind FHE. Not sure what could be done with it at 7s though hah.
- e12e 4y agoCurious if there's tooling to de/serialize the encryption context? 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.
- slackner 4y agoThere seem to be built-in methods for serializing and deserializing crypto context as well as ciphertexts [0], so it shouldn't be too difficult to build a "complete" example that performs the actual computation in a different application. That said, with a duration of 7 seconds for a simple addition, it is still far from many practical applications, in my opinion. [0] https://github.com/openfheorg/openfhe-development/blob/main/src/binfhe/examples/boolean-serial-json.cpp https://github.com/openfheorg/openfhe-development/blob/main/...
- touisteur 4y agoWould that enable continuations or lightweight checkpoint restore? If computation takes hours or weeks you might want to do add some restart-ability...
- j2kun 4y agoWe have some serialization and deseralization to protos for internal tests. It's straightforward, and probably we'll add it to the compiler once we have a strong need and some more stable backends
- fnordpiglet 4y agoSomeone needs to make a crypto network that runs submitted FHE programs as proof of work.
- __MatrixMan__ 4y agoWhat's to stop somebody who knows the cleartext (because they submitted the job) from cheating?
- fnordpiglet 4y agoThey would presumably pay for the computations on the network (by paying gas). The output would be still encrypted with the FHE public key and can be signed. Having the clear text is the same as having the private key. How would someone cheat? I’ll admit I’m no crypto nerd but I’m not sure how you would cheat.
- friend_and_foe 4y agoThey'd pay themselves for computation on the network? You can't see a game theoretical problem with this? 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.
- __MatrixMan__ 4y agoThe cheat would be: 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.
- molsongolden 4y agoHas anyone used Vaultree[0]? Their product is FHE-as-a-Service and they claim "near plaintext speed". 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. [0] https://www.vaultree.com/how-it-works/ https://www.vaultree.com/how-it-works/
- whatshisface 4y ago"Encrypted queries for an encrypted database" could be as straightforward as encrypting both the keys and values using a known public key and putting the results in MySQL. You have to be careful with the claims made around these kinds of things because they often appear to be more complex than they are.
- hn_throwaway_99 4y agoHuh? How would you search on any encrypted fields?
- KMag 4y agoNo subfield matches, no comparisons other than == and != on the whole field, and only works with deterministic encryption... so leaks like a sieve under many threat models.
- admax88qqq 4y agolol no it's not. 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.
- amadvance 4y agoEven lookup is not easy to be done securely. You don't want that a malicious server/database knows that you are accessing always that record. See this discussion about how to achieve that: https://news.ycombinator.com/item?id=31668814 https://news.ycombinator.com/item?id=31668814
- deleted 4y ago[deleted]
- tener 4y ago> Finally, encrypting each bit of a plaintext message comes with major tax on space usage. Each encryption of a single bit corresponds to a list of roughly 700 32-bit integers. If you want to encrypt a 100×100 pixel greyscale image, each pixel of which is an 8-bit integer (0-255), it will cost you 218 MiB to store all the pixels in memory. It’s roughly a 20,000x overhead. For comparison, the music video for Rick Astley’s “Never Gonna Give You Up” at 360p is about 9 MiB (pretty small for a 3 minute video!), but encrypted in FHE would be 188 GiB, which (generously) corresponds to 20 feature-length films at 1080p. Ouch.
- deleted 4y ago[deleted]
- forty 4y agoIs there proof that this is secure? (ie that no information can be found on the plaintext when only having the ciphertext?) I'm hoping something of the like of "this is secure if AES is secure"
- blibliblo 4y agoI could not find on which algorithm this compiler is based at first sight. I know of an other library for homomorphic encryption Lattigo (https://github.com/tuneinsight/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 https://eprint.iacr.org/2015/939.pdf
- j2kun 4y agoIt's based on the "Learning With Errors" problem and it's relative, "Ring Learning With Errors", both of which have reductions to lattice crypto problems, the same sort that are in the new NIST proposals for post quantum cryptography. See this article for some more info about how security is evaluated: https://jeremykun.com/2022/12/28/estimating-the-security-of-ring-learning-with-errors-rlwe/ https://jeremykun.com/2022/12/28/estimating-the-security-of-... That said, the compiler itself doesn't use any crypto. It generates code for a backend API, and the backend implements the FHE scheme
- yafbum 4y agoThe application domain for this stuff is so negligible... Who's going to pay for this huge added cost? 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.
- fhd2 4y agoI've been working in the privacy space for a few years and always had the same opinion. If a customer doesn't trust the data processor, the logical conclusion is to not send any sensitive data at all, which is technically possible. But it means more edge processing, more client side processing, most likely not what Google wants. But they have to do _something_, even if nobody uses it in the end.
- yafbum 4y agoThe practical way that people deal with this is putting a swarm of auditors all up in the processors' business. It used to be this way for telecom as well: to know whether comms were secure, you needed to walk the length of the cable and look for taps. Comms encryption has radically changed this. The question is, is there a similar revolution in the making for processing as opposed to comms. I strongly doubt the benefits will outweigh the drawbacks.
- jossclimb 4y agoThat's not the only trust model at play. Here is a different example of where FHE becomes very useful. 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.
- CGamesPlay 4y agoHmm, given that "mov is Turing-complete" [0], is it possible to get around the requirement that loops must be fully unrolled? Obviously you couldn't tell if your algorithm was finished, but if you could ask the key holder if the algorithm had completed or needed more work, you could theoretically compute any algorithm. What am I missing? [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? [0] https://drwho.virtadpt.net/files/mov.pdf https://drwho.virtadpt.net/files/mov.pdf
- smasher164 4y agoCombinatorial circuits aren't turing complete. The novelty of mov being turing complete is that they were able to do conditional branching with just loads and stores. In the FHE case, they can't read and write to parts of memory, so it's a no-go. This is why their compiler essentially only works on pure functions whose inputs have a statically known size.
- jchw 4y agoThe "mov is turing complete" thing is mostly about x86 mov having a lot of functionality. It can do arithmetic. The mov mnemonic basically encapsulates a bunch of functions (and opcodes), kind of like how git checkout can do at least ~3 distinct operations depending on arguments. 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.
- Charlie_26 4y agoI may have misread the title and thought that was one bigoted compiler
- fatneckbeard 4y agosounds like you could have anonymous currency. 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.
- CraigJPerry 4y ago>> 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 https://www.federalreserve.gov/monetarypolicy/reservereq.htm
- aspyct 4y agoOther countries exist.
- eru 4y agoSee https://en.wikipedia.org/wiki/Reserve_requirement https://en.wikipedia.org/wiki/Reserve_requirement 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.
- PeterisP 4y agoIt's not really about the reserve requirements, but about basic accounting requirements, which all banks do have. At its fundamentals, bank balances are not some storage of "your money", they are recording of how much the bank legally owes you (or vice versa). And of course the bank has to know exactly what liabilities they have according to their contracts, so they need to see the balances. They also need to be able to add arbitrary quantities of new money to the FHE scheme when cash is paid in and remove it when it is paid out.
- golol 4y agoWhen I first learned about homomorphic encryption it gave me the idea of "cryptographic AI", as some sort of sci-fi writing prompt. Suppose compute is readily available to interstellar civilizations but actually designing a (super)intelligent AI is difficult. Then it could be economically feasible for cryptographic AI to exist. These are descriptions of AIs that run under homomorphic encryption, where the private key is only known by the AI itself. The description of the AI program and its state is spread throughout many locations and generally runs in a decentralized way. Planet earth might receive a segment of a cryptographic AI and make deal: Earth executes the program with some inputs it may choose to compute a solution to a problem. The program can be given inputs via a public key. The execution of the program can not be modified or manipulated since it is running under homomorphic encryption. What the AI gets in return is that earth provides it with additional compute that it may use for its own purposes. Earth furthermore allows the AI to transmit updated fragments of state into the stars. Over the course of many years, the pieces of state of the decentralized AI spread throughout the galaxy combine to represent the thoughts and actions of a singular entity. If earth modified the computations then the transmitted state could cryptographically be seen to not be valid, and hence would not be used in the decentralized galaxy spanning computation of the AI. Furthermore if earth cheats the AI in the deal then there may be consequences such as relativistic kinetic kill projectiles.
- MoOmer 4y agoPut a few thousand more words to pad, and I’d read that book!
- golol 4y agoYea collecting sci fi ideas is fun but writing a book is wayyy too hard sadly ...
- addandsubtract 4y agoThere's an AI for that.
- stjnvcm 4y ago
- gigatexal 4y agoThis is all interesting and I’m thinking now with all the talk of privacy and data sovereignty etc why this is coming out or Google now and not Apple? Anyone know if Apple is thinking along these lines? Would be nice if we could get performant computation on things without having to decrypt our own data. Then again my understanding and real world applications of homomorphic encryption is pedestrian at best. 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.
- londons_explore 4y agoThe news stories you read about Google and Apple re: privacy are heavily influenced by corporate PR departments sending 'tips' to the media to try to make themselves look good or a competitor look bad. The actual privacy efforts of both companies don't (in my experience) closely align with what the news says about them.
- Uftos 4y agoWhy it's a compiler and not a library
- noman-land 4y agoI left this comment on the blog but I'll repeat it here as well. 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?
- nabla9 4y ago> It’s roughly a 20,000x overhead. 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)
- cfuendev 4y agoAm I the only one who read this as "Google's fully homophobic encryption compiler"?
- Aachen 4y agoAs the old logicians joke (https://www.barrypopik.com/index.php/new_york_city/entry/three_logicians_walk_into_a_bar https://www.barrypopik.com/index.php/new_york_city/entry/thr...) goes: I don't know.
- bunnyswipe_com 4y agoThe future is bright
- codethief 4y ago> First, the subset of C++ supported by the compiler is rather small. As mentioned earlier, all data needs to have static sizes. This means, e.g., you can’t write a program that processes arbitrary images. Instead, you have to pick an upper bound on the image size, zero-pad the image appropriately before encrypting it, and then write the program to operate on that image size. In the same vein, the integer types you choose have nontrivial implications on performance. To see this, replace the int type in the 32-bit adder with a char and inspect the resulting circuit. > 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, …).
- j2kun 4y agoAdmitting the possibility of having multiple frontend languages for the compiler is a longer term goal of mine!
- antognini 4y agoI have a very basic question about fully homomorphic encryption. As I understand it, the encryption scheme ensures that an adversary who has access to the physical computer cannot determine what data the computer program is operating on, even by inspecting the physical states of the machine. 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?
- ChadNauseam 4y agoIt is possible to determine what algorithm is being run. To prevent that as best as possible, you want Indistinguishability Obfuscation.
- phkahler 4y agoIs there any way to get unencrypted data in or out? I'd like to feed it real-world data and get real-world data out, but not know the internal state.
- DjvuLee 4y agowhy not using the python as the input source? Since most people write program using python nowadays, this may lead to a bigger impact.