The Rise of Fully Homomorphic Encryption
queue.acm.org
queue.acm.org
Is there any comparison performance benchmark for these Cornami chips on real world algorithms? The data given by https://cornami.com/fully-homomorphic-encryption-fhe/ doesn't really help me.
To give you sense of performance, today you can multiply 2 encrypted 8192-bit values in BFV with typical (not optimal) scheme parameters in 17ms on a single core of an M1 Macbook Air. This is the most expensive operation by a wide margin. The ciphertexts for these parameters is about 0.5MB and the keys are maybe a meg or two.
The algorithm you want make fast for most schemes is the Number Theory Transform (NTT), which is basically a Fast Fourier Transform (FFT) for finite fields. This algorithm has only O(nlog(n)) operations, so the computational intensity relative to memory accesses is fairly low. This stands in contrast to something nice like matrix multiplication where matrices are O(n^2) but require O(n^3)[1] computation. Unfortunately due to Amdahl's law, you have to make not just NTT fast, but all the other boring O(n) operations schemes need to do.
If you want to make FHE fast enough to justify an ASIC, you'll have to avoid data movement and basically keep everything in on-chip SRAM. Waiting 400 clock cycles for data is a non-starter. For algorithms with bootstrapping, your bootstrapping key might be 100MB, so you'll probably want a chip with like 512MB of on-chip memory to hold various keys, ciphertexts, etc. You then need to route and fan-out that data as appropriate.
You then need to also pack a ton of compute units that can quickly do NTTs on-chip, but are also versatile to do all the other "stuff" you need to do in FHE, which might include multiplication and addition modulo some value, bit decomposition, etc. And you'll probably doing operations on multiple ciphertexts concurrently as you traverse down an arithmetic or binary circuit (FHE's computational model). Figuring out the right mix of what an ALU is and how programmable it needs to be is tricky business.
For larger computations, maybe you stream ciphertexts in and out of DRAM in the background while you're computing other parts of the graph.
Making an FHE accelerator is neither easy nor cheap (easily a 50-100M+ investment), but I think it is possible. My SWAG is that you might be able to turn the 17ms latency into like 50-100us but with way more throughput to execute a large circuit graph(s).
[1]: Strassen algorithm git out of here
Are there any companies doing pioneering work on this now? What aspects of FHE does your employer do? How would you say the future is looking for FHE?
My impression is that there are many parallels computing at large where custom hardware is becoming more and more prevalent. You can run arbitrary C programs with FHE by building a CPU out of binary gates and running on that, but it will run at 1Hz[2] emulated on 8GPUs. So, computing fibonacci(5) takes like 16 minutes. Conversely, you could create an arithmetic circuit that does it in like 16us. However, working with circuits is hard, let alone the additional requirements FHE imposes.
Today, our compiler lets you write Rust code that turns into an arithmetic circuit in the BFV scheme. It also manages parameter selection, which is another annoying part of FHE: choose parameters too small and decryption will fail due to excessive noise, but larger parameters slow down the computation and make ciphertexts larger.
Overall, the FHE has a ton of promise, but is currently in the chicken and egg phase whereby there isn't much commercially available because there isn't a market because there isn't anything available. We're trying to be an egg and grow along with a market. FHE is a big area and there's a ton to explore, like multi-key encryption[3]. FHE is currently nascent, but I believe its future is bright where it can be appropriately used.
[1]: https://docs.sunscreen.tech/
[2]: https://www.usenix.org/conference/usenixsecurity21/presentat...
Old man shakes fist at clouds.
Would practical FHE be interesting? Sure. Is it happening? Doesn't seem like it is any time soon.
I think the title maybe a little too optimistic / vague by saying it's "near" without indicating what else is needed to get there / when it might happen ;).
With a symmetric cipher, I could figure out the blood type of every employee pretty easily. With an asymmetric cipher, I could figure out everyone who has my blood type, and the blood types of anyone who reveals that information.
If the point is to filter data when you aren’t allowed to know what the data is, then the act of being in the filter or not reveals some of that information. It’s just a game of twenty questions.
In the FHE model, the assumption usually is - you have some data, someone else does some encrypted calculations, you get the encrypted answer back, you decrypt the answer and read it. The adversary cannot play 20 questions because they only calculate the encrypted answers, they are not allowed to see what the answers are.
Do you by chance have a simple way to explain how the search works then? Because superficially it seems like you might assume that you're looking for Enc(pk, m') == Enc(pk, m) and apparently that does not work.
Suppose Bob has an array of data he arranges into an mxn matrix, A. This data is not encrypted, but is encoded appropriately. Note that many FHE schemes allow you to compute ciphertext-plaintext operations.
Alice can send him 2 vectors x and y encrypted under her key, where x and y are all zero except for single 1. Bob homomorphically computes Ax = b. Since x is all zeros except for element i, the operation Ax effectively selects the ith column of A. Bob then computes dot(b, y). Since y is all zeros except for a 1 at element j, the dot product effectively selects the jth row of y. Bob sends the dot product back to Alice, which due to FHE is still encrypted under her key.
Alice decrypts the result and has looked up the j,ith element in A without Bob learning Alice's query or which data was involved in processing her search.
The default program on the Sunscreen[1] compiler playground shows this exact algorithm.
Disclaimer: I am an employee of Sunscreen.
If you'd like to check it out yourself, feel free to take a look at our team's FHE compiler and playground [0].
I've never seen a saas product that isn't using and/or "sharing" their customer's data for their own benefit somehow. If they exist at all, they're the exception and not the rule.
Saas seems a lot more predatory and risky than most products/services. You hand over money, you hand over control, you hand over your data and all of it leaves you varying degrees of vulnerable.
I guess I shouldn't expect a pragmatic view of saas to be popular around here (some of you are likely working on your own saas projects after all), but the reasons saas is attractive for companies to offer are the same reasons that make me hesitate to use them.
FHE does have potential applicability here, but i think the potential is a bit overblown because there are a lot of devil in the details issues.
The only problem is that there's a large performance penalty still, though there has been major progress in making it more efficient.
Also not an expert here, but if "Valuable insights through AI (artificial intelligence), big data, and analytics can be extracted from data", then you'd be a fool to believe this will protect your privacy, right? Or am I missing something? I want encryption that protects me from corporations, not encryption that protects the data corporations have from us and ups their surveillance game. I guess it's no coincidence a lot of research seems to be done by M$.
It goes on to grossly overstate the extent to which current IT systems are at risk as well as the extent to which FHE would even address actual IT threats. Plus, anytime anyone claims something is “provably secure”, they are leaving out crucial parts of the system, like the interface with humans or key rotation.
And then there’s the part where the author is a VP of business development at a company that makes FHE hardware. Sigh.
A few years ago there were papers on evaluating simple logic circuits in an FHE context and it took 2h hours for what was basicially 5-6 NOR gates.
As (maybe weak) evidence the progress on practical implementations of PCPs/SNARGs
Our team has been working on making FHE more accessible to engineers via a compiler; we've found usability to be a much bigger obstacle than performance.
You might be surprised to see how far performance has come! For (an admittedly small example of) matrix-vector multiplication, we can do key generation, encryption, computation, decryption, and compilation in less than 5 seconds on a MacBook [0].
Take this for example
"Valuable insights through AI (artificial intelligence), big data, and analytics can be extracted from data—even from multiple and different sources—all without exposing the data, secret decryption keys, or, if need be, the underlying evaluation code."
FHE gives you NO guarantee about the code that is running on the encrypted data. I can run a leaky AI model or a SELECT * on encrypted data and still get the output. What I can do (and that's assuming there is open-sourced, auditable code) is to make sure that anyone with hypervisor access on that machine cannot dump my data out during processing.
A very powerful concept for remote processing, supply chain security, and overall reducing trust; but completely unrelated to privacy.
I might be misunderstanding but i think this is misleading. Any code can be run, but the person running the code cannot see the results (or any side effects), so they cannot leak data.
If by person you mean the admin of the machine, then yes. If by person you mean the developer of the FHE-based application, then "maybe" If by person you mean the analyst who would in the end order an AI python model to be executed through the FHE-based software on a machine. Then no, that person will in the end get back human-readable results. Be that a model, or a table from an SQL DB running in FHE
Maybe someone who has actually studied homomorphic encryption can chime in.
For example: I run an ML model using FHE on some data I shouldn't have access to in plaintext. The expected outcome of this workflow is a trained ML model on that data. FHE tells me nothing about the quality of this model. It could as well be an overfit model that spits out all the sensitive data.
Edit: Okay so I might now understand you refer to a scenario where the user submits their data in homomorphic form to the cloud, where an AI model is trained on it. The AI model parameters are later returned to the user's device, which then decrypts them with the user's key and executes a classical model with those parameters, and then resubmits the user's data after processing with the said ML model (unencrypted) back to the cloud. It's true the user usually has no way of auditing the code / model that runs on their device, but isn't that rather easily alleviated by opening up the APIs for communicating with the cloud part of the service?
A more real-life example.
I am a pharma company and I want to execute a query on some hospital data. The hospital doesn't want to give me the data in plaintext but they are fine with me getting some aggregate insights from their data that are not PII.
Now lets assume I decide to do that using FHE. I can now compute my query on the encrypted hospital data and I never see the plaintext data.
What do we "win" in this scenario? We can do this computation wherever we want because no matter where the computation is done, the data will be encrypted, so no risk for the infra provider to see that data.
What we don't "automatically win" in this scenario? 1. Guarantees that indeed I am running an SQL query on that data and not something else along with it -> That is only possible to guarantee if the FHE software is properly audited (same with any software tbh, but easier with FHE and similar techs because of the integrity guarantees due to encryption). 2. Guarantees that the SQL query I made will not leak patient data in the end (through linking additional data, or diff attacks) (same with any other SQL query)
People who are deep into these technologies will say "yes of course" thats not an FHE problem. And that is true. But every FHE vendor I've seen blur that difference by not specifying what kind of attacks they protect against when they talk about "protecting privacy".
Heck, most of them they don't even talk about the attestation process and how their clients can make sure that they can trust the software running in encrypted form. Yes, these hold true for all software, but the point (for me) of encryption in-use is to make sure we hold software to a higher trust standard than today, not just replace a trusted party with another one.
> But every FHE vendor I've seen blur that difference by not specifying what kind of attacks they protect against when they talk about "protecting privacy".
Agree with you here. FHE is an impractical technology at this stage. I'm pretty sure all commercial FHE vendors are borderline scammers, and have a loose relationship with the truth.
What is FHE actually good for then? Let's imagine you are a top secret agent and you get instructions to fly to Bulgaria as a part of your mission. You have other hostile agents constantly monitoring you, trying to understand your next move. But there's a problem - to buy a plane ticket to Bulgaria you need to know the name of its capital city. You can't just type it to Google, because these other agents have actually infiltrated the Google servers and can see everything you search (assume once you actually know the name of the capital, you can somehow buy the actual ticket without "them" knowing..)
Lukcily though, CloudCorp offers a public homomorphic query service for all world capitals. This service allows you to send a query for the capital of any country over an intercepted connection, and get back the result. Even if the hostile agents had infiltrated CloudCorp and were monitoring all your comms, they would not be able know which country's capital you just queried. Not even CloudCorp could do that, you are the only person who knows what you asked and what was the result.
How such service would be implemented is explained in good detail in this tutorial, completele with working code: https://github.com/homenc/HElib/tree/master/examples/BGV_cou...
P.S. The capital of Bulgaria is Sofia.
The other way I read what you’re saying you’re saying the holder of the model after they decrypt it may not be trusted with the model or the original data. But they hold the decryption key to both. So, why did you share the key to someone you don’t trust? That breaks the model too.
In any sane deployment of FHE the key holder is the person who owns the data, not the app developer and not the person "running" the program.
It is still related to privacy, but the privacy "attacker" is the execution place, allowing for outsourcing of computations and storage without running into data leaks or violations of data protection laws.
Maybe you use a different definition of privacy?
Yes, when I wrote the comment I had in mind "output" privacy while FHE is dealing with "input" privacy. It is related to privacy, but not in the way most people think about it.
If you go to a random person and ask them about privacy they will not think about the threat model of a cloud provider leaking their data, but they will think of the thread model of a pharma company knowing exactly what drug they bought and when. That notion of privacy is not covered by FHE(alone). And even the first notion of privacy is covered only if the FHE program has a way to attest itself so you know that what you expect to run is indeed what is running.
You mean in order to validate the data is authentic? Otherwise the code running on the data is irrelevant, as it can't access the data itself (and thus preserves the before-mentioned privacy).
I'm open to correction, but it's my understanding that the strongest form of FHE allow users to submit an encrypted executable with embedded data as input, which is then processed by an untrusted server. I'd definitely call it an ultimate form of privacy. The computational cost is prohibitively expensive, and conditional branch is impossible in the standard implementation, so it's largely an academic exercise. But last time someone on HN told me currently the achievable performance on a modern computer is roughly equivalent to a 1970s mainframe, so I guess some niche applications are still possible.
Weaker forms of FHE don't have this level of privacy, and they do not claim so. Nevertheless, relevant development still represents progress on cryptography and privacy researches as a whole.
In this case the real danger is that the availability of "privacy-preserving technologies" like FHE, MPC and Differential Privacy will actually do more to undermine human privacy than all the non-confidential tech that come before. This will mostly occur by allowing corporations to build sophisticated statistical/ML models using data that would previously never have been allowed out of its confidential silo.
That's the point though isn't it? Only the person who wants the results can get them or even see the inputs. That restricts the data available for shitty AI and precludes any Joe Schmo from scanning the whole database.
If your threat model is instead that you don't trust the FHE endpoint, then much how you want HTTPS termination to happen in a place you control you also in this case just encrypt the stuff you care about on your own devices.
Suppose you have multiple organizations that want to run some computation on their joint data, without revealing their data to each other. Each organization has their own machine that runs the MPC protocol. They have full control over their machine, and can inspect that the code correctly executes the protocol. Only once all organizations agree, will the computation take place, and within the security model of the protocol, it is guaranteed that only the correct computation output is revealed to the designated parties.
Your scenario has these parties, 1) a patient whose data we're discussing, 2) the hospital they shared it with, and 3) a pharma company looking to use the data. The hospital wants to promote this use without leaking any PII.
You're right that the hospital has no idea about the queries ("the code") but they control the server and which messages it will send in response.
As you point out, the hospital wouldn't run a FHE database capable of full-text extraction specifically because that would amount to simply sending all the data to the pharma company.
Instead they'd run a specialized FHE-DB server which would, for instance, return only row counts. The pharma company would run secret queries and if the hospital had one or more patients who matched the query the pharma company would know to the contact the hospital and then once paperwork is signed they could rerun the query with a signed token from the hospital and finally the query would return the actual PII.
I feel FHE combined with slightly cheaper cost might enable things like community run server-less apps that have user state stored and processed by untrusted nodes with persistent state stored and accessible only by the data-owner. E.g. a simple excel-esque web app which only serves the UI while State and calculations are running on this hypothetical system at no cost to the apps creator with me paying only for exclusively my usage. They provide the code but no one but me can extract my data and the results of any computations, and for the privilege I pay the system.
I miss the days of upload and forget software that just relies on client resources and so require little upfront investment from developers, I feel FHE plus distributed computing could enable this.
I am aware "Web3" claims to want this future as a concept but the cost and utter lack of confidentiality (I can observe all data to and from a contract as well as the sender/receivers identity) makes it a super-niche borderline useless VM. For distributed governance sure, it's a public ballot box (the preface to the first distributed systems example, a single account with credits), but for any application/user data absolutely unacceptable.
Examples include government agencies who used made up in-house encryption schemes to get their data sharing plan past their legal privacy and security gates and then there was a secret key a small cadre had who could unscramble it after it was distributed in the sector, researchers rejecting synthesized data for uncontrolled test environments because "it was too hard," when really they just wanted the data sets outside the legal controls on it, rejecting differential privacy queries because they didn't want to come up with or specify their queries first based on metadata and again just wanted the data, rejecting identifying the individuals with access to millions of peoples health information data because as institutions they felt entitled to it, banks and payment firms rejecting zero knowledge proofs of user attributes because it violated KYC, and these are just a few.
There has been a concerted effort to squeeze the data toothpaste out of the tube when it comes to health information and other types, and so I am ambivalent about FHE use cases because its primary use case is side stepping rules that protect the privacy of data subjects.
The question I would have is, if data synthesis, legal risk-based de-identification, differential privacy, and cryptographic tokenization protocols were insufficient, what technical improvement in actual accountability does FHE offer to data subjects, and given the size of the data sets this facilitates, what are the consequences of its failure modes?
Given the entire history of cryptography is defined by one party convincing their targets that a given scheme provides them security, the way that FHE scales to giving data collectors impunity "because it's encrypted!" seems like it is vulnerable to every criticism leveled at blockchains, where just because it's encrypted doesn't mean it isn't laundering.
I don't think FHE is primarily aimed at privacy use cases anyway, more at ways of cooperating etc. where transparency could be detrimental to some or all parties.
Not to mention, if you are outsourcing data computation, presumably its a lot of computation or you would do it yourself, so the overhead seems extra important in that case.
The most convincing case i've heard is blockchain stuff - where everything is distributed to non trusted parties. (Normally i hate bitcoin hype, but maybe FHE would let you do something interesting with it)
You may let people store homomorphic data on your servers and even run your algorithms on that data, but you have no way of handling customer complaints or fine-tuning / debugging your service because you can not understand ANY of the customer data you are storing.
Similarly, blockchain sounds like a good idea until you need to reverse a transaction: https://www.pcmag.com/news/cryptocom-sues-woman-after-accide...
It doesn't. Because its not aiming at solving these problems. Encryption in-use is aiming to solve trusting hardware (and maybe code) you don't own. Privacy is a different (IMO more complex) problem.
You did some experiments with HE in 2019 and it involves orders of magnitude slowdown — thousands of times slower than regular computation. I don’t see this speeding up either.
And that, differently, for each access (write and read) to each cell in the table.
Not what you would say feasible right now.
And for a more tangible demo of FHE, we built open-source webapps that let you privately browse Wikipedia [2] or look up live Bitcoin address balances [3]. This is FHE running in the browser today, returning results in seconds.
[0] https://eprint.iacr.org/2022/368 (disclaimer: this is our paper)
General FME computation is obviously not likely to be practical or cost effective any time soon, but there may be some specific use cases, like querying a database, where hiding the information you want to know from the server is advantageous. There are adversarial environments where knowing the information your adversary is interested in provides a competitive edge.
I'm curious to dig more into their implementation.
> https://www.zama.ai/post/titanic-competition-with-privacy-pr...
Its main ambition is to show that FHE can be used for protecting data when using a Machine Learning model to predict outcomes without degrading its performance.
Disclaimer: I'm working at Zama (cited in the article posted).
> https://fhe.org/fhe-use-cases
Also anyone can contribute and add resources as it lives on an open source github repo.
I knew someone who was responsible for delivering backups from a secure data center to a lockbox every couple of days. Unfortunately the bank was only a few blocks from the data center so I'm not sure how much physical separation that really provided. Also this particular person would have been able to do absolutely nothing about being mugged for the disks if someone actually cared. But maybe I'm a little too paranoid.
I recall once having to drop the night's deposit off from the restaurant I worked at. They were down a manager due to illness, it was on the way home, I was a figurative if no longer a literal boyscout, so the math on "shenanigans if hinkley leaves with the money" versus "shenanigans if there is no night manager in the store" apparently leaned toward me. I'm glad they trusted me but I was a nervous wreck for four blocks until that bag went into the night deposit box.
Anything that can move "precious cargo" without a human failure mode is alright in my book.
This - "set {XOR, AND} is Turing complete" - is incorrect. You need to also have "true" constant.
More importantly, FHE and post-quantum crypto are two completely orthogonal topics.
Homomorphic is the property that (classical or quantum) computation can be performed on the encrypted (classical or quantum) data without decrypting it. Homomorphic encryption with classical data on classical computers is rather difficult and fascinating. Homomorphic encryption on quantum computers is trivially easy (if you already have a standard scalable quantum computer, which do not exist yet).
"Post-quantum" is the property that a classical computer can efficiently perform encryption that can not be broken even by a quantum computer.
Today, if I understand it correctly, that means the encryption can't be broken on a computer with resources < whatever is required to calculate the square root of 16 ;)
for health data, this is a game changer in so many ways
Usually the cloud will have access to your model. That poses a problem if your model is highly sensitive. (Imagine the NSA wanting to run a model on North Korean servers. NK would immediately snatch up that model.)
With FHE, you can theoretically avoid that. Someone can upload an encrypted model to the cloud. The cloud can do some computation on it (inference) and deliver an encrypted result. Then you can decrypt the result in the comfort of your own government^Whome.
Obviously this is a bit of a stupid example, but just think of all the scenarios right now where you'd want to offload your computation on someone else, but you don't want to let them see the computation.
Two identical cleartext values would likely not encrypt to the same ciphertext value (for example, you could get around that easily on the client end by simply incrementing any duplicate value by 1 before sending and then decrementing it by 1 again on return, assuming that is done undoably given the other operations happening); any comparison operation would also likely be encrypted and thus unknown to the server; so the server couldn't just linearly compare any two encrypted values to make deductions.