Fully Homomorphic Encryption (FHE)
github.com
github.com
If you send your server two encryped numbers and ask to multiply them for you, the server may send you their addition instead, or just encrypt some constant it chooses and send you that. And you can't check that your data was processed the way you want.
If you want authenticated FHE, that will be even slower.
For anyone who wanted a database to query privately, you can look at dishonest majority generic MPC protocols. Here, you will need N servers instead of just one. You will secret-share your inputs between them, and let them do computations on the shares. As long as at least one of the N servers is acting in your interest, you are safe. But if all servers unite their shares, they can recover your values.
That's not what FHE intends to solve. You have the exact same problem with any kind of remote processing, encrypted or not. I don't see why you think it's important to point out the obvious.
Gnull just pointed out that FHE by itself does not provide authentication so you still need some additional means to achieve that.
With the use cases of FHE though that just is not a major downside. Instead if you rely on some consensus protocol you can get a reasonable guarantee of correctness. If a random N out of M available operators are selected and all produce the same result or hash of a result, you can be reasonably sure that the expected operation was performed.
Additionally, as the "master" who can actually read the FHE data, for most non-trivial tasks I suspect there is often a proof or heuristic you can use to reasonably judge whether the result is correct or at the very least reasonable which should stave off a significant portion of the avenues for attack.
Trusting the server to perform the operation I asked it to is an entirely different domain than trusting the server with the knowing the input and output data of the operation.
Well put.
While trusted computing could be used for such verification, I'm not aware of any commercial real world implementation. I'd be genuinely happy to be made aware of one, though, so please feel free to point me to one.
Suppose you did this and encrypted + signed your values with FHE and FHS as Sign(Encrypt(x)) and Sign(Encrypt(y)). Now you want to add x and y. For that, you will have to run the homomorphic addition of Encrypt(·) values using homomorphic operations of Sign(·), i.e. you do Encrypt(x) + Encrypt(y) inside Sign(·), not just x + y.
This means that the overheads introduced by FHE and FHE do not just add up, they get composed (as in composition of functions). This will be a terrible blow-up in performance. I guess, for this reason people try to build authenticated FHE that will have the properties of FHE + FHS but as a one, more efficient block.
I don't see how authenticated encryption would address that. In fact, I don't see how any kind of encryption can address that. Every way I can see to verify that the server is actually carrying out the correct operation would work without encryption.
Authentication proves that you are talking to the right server and that the result you got back from the server was the result it tried to send you, but whether or not that was what it was supposed to send you is out of scope for encryption.
When it comes to FHE, there are 3 underlying paradigms you can target with compilers:
1. boolean circuits, where you represent your program as encrypted boolean gates. The advantage is that it's as generic as it gets, the drawback is that it's slow. TFHE is great for that, and it's what is shown here.
2. arithmetic circuits, where you represent your program as a combination of encrypted additions and multiplications. This goes much faster, but you are quickly limited in terms of usecases because you can only do a certain number of arithmetic operations. CKKS/SEAL targets that: https://www.microsoft.com/en-us/research/project/microsoft-s...
3. functional circuits, where you represent your program as a combination of homomorphic functions. Advantage is that you can do very complex things like deep neural network, the drawback being that you have limitations of the bits of precision for the computations. Concrete targets that: https://zama.ai/concrete/
- With boolean circuits you need to run dozens of boolean gates, which means a lot of underlying crypto ops. Works but expensive.
- with arithmetic circuits, you would approximate it using polynomials. Works but not with high precision.
- with functional circuits, you encore the function as a single “bootstrapping” operation. Works in a single crypto op.
Performance / precision tradeoffs will be very different in these 3 cases
I first encountered FHE many years ago, but while the concept is cool, the performance hit (IIRC I saw literally a million times slowdown back then) made it absolutely impractical for non-toy problems. And whenever I see reports, they tend to note that it's slow, just as this project (https://github.com/google/fully-homomorphic-encryption/tree/...) notes "the run-times of the FHE-C++ operations are likely to be too long to be practical at this time.", it does not provide any data on just how slow it is.
Are there measurements on how long the demos take to execute, so that I can evaluate if it has the potential for some specific idea without having to set up the build system to try it out myself? E.g. run the same string capitalization demo on 100, 10 000 and 1 000 0000 characters to benchmark its speed.
So a ~40-year regression in performance.
Calling this a "regression" is nonsense.
I was thinking of the later chips in the 68k series, which got much faster over the years.
My view is that this is already fast enough to support use cases that really need the unique capabilities of FHE. Since this work we've been focused on making FHE more usable with compilers and tooling [3]. Currently most FHE is being programmed like that Intel 8087 was: with the equivalent of assembly by directly calling functions in FHE libraries to perform arithmetic and crypto operations. Imagine having to do register allocation by hand for all of your code. The EVA compiler [4] is meant to be like a "C compiler for FHE", hiding low-level crypto concerns and providing common optimizations.
[1] "CHET: Compiler and Runtime for Homomorphic Evaluation of Tensor Programs": https://arxiv.org/pdf/1810.00845.pdf
[2] https://en.wikipedia.org/wiki/Intel_8087
[3] "EVA: An Encrypted Vector Arithmetic Language and Compiler for Efficient Homomorphic Computation": https://arxiv.org/pdf/1912.11951.pdf
Single core: 2838.660s (47.31 minutes) Multi-core: 843.828s (14.06 minutes)
The multi-core version was using four CPU cores, so slightly worse than a linear performance increase. Both versions lit up the fans in my MacBook Pro pretty hard.
The string in question, by the way, was "hello" -- five characters long.
Does this terrible performance match your previous findings? It is so bad I'm wondering if there is something wrong with my dev environment.
I'm curious if this approach could be used to build database indexes, and if so, whats the performance cost in using it?
I read about an approach a few years ago which needed hundreds of milliseconds of computation for simple operations. Has the state of the art improved?
I will also note that for efficiency, Oblix relies on Intel SGX. I’m not sure if a purely cryptographic solution can provide the same security and efficiency properties.
Google still relies on the same group you read about, probably. From the docs:
> This transpiler connects Google’s XLS library to the TFHE library.
On the TFHE website (https://tfhe.github.io/tfhe/):
> Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.
Good question about database indexes; that could be an interesting use case study.
> PALISADE now supports the BGV, BFV, CKKS, and FHEW schemes and a more secure variant of the TFHE scheme, including bootstrapping.
Maybe PALISADE is not user friendly enough? Just a wild guess I never used PALISADE
https://github.com/google/fully-homomorphic-encryption/blob/...
It's such a convenient parody of a classic programming exercise that it must be intentional. I can't help laughing at how that one file is saying two things at once:
"Uh, it's one-word Hangman. Dead simple. Nothing up our sleeves. I have Real Stuff to do, give me a break."
"Our product is working great, but there's some minor fixes to do. Let's hold a meeting on how to really get this multi-word support cracked. Maybe add 'privacy-aware' and 'digitalization'?"
Surprisingly, it's also making it very easy to understand what is actually relevant in the project.
Microsoft/EVA - https://news.ycombinator.com/item?id=25193863
Alchemy - https://news.ycombinator.com/item?id=18265948
Cingulata - https://news.ycombinator.com/item?id=23437737
And a good overview of HE compilers/libraries https://arxiv.org/pdf/2101.07078.pdf
Electronic voting is tangential.
Encrypted storage for random cloud services should be at least decades away.
Of possible interest is a design for an online deliberation system:
https://bytebucket.org/djarvis/world-politics/raw/master/doc...
HE would be useful to help hide the votes.
It's slow, you would not want any part of your program that isn't security critical using it.
Methinks this has interesting implications for storage-optimizations: in many situations we will significantly-optimize for certain use-cases at the expense of others (e.g. O(1) or sub-O(log n) retrieval at the cost of super-O(log n) insert or modifications) - but because now you know your program cannot appear to operate faster than O(log n) for any operation you could de-optimize some parts of your program which in turn allow you to improve sub-O(log n) parts to be O(log n), e.g. insert/update performance.
Let's say you have a sorted array, and try to do a binary search. For each 'if', the only way to calculate it is to take both branches and combine them later. So for x branches in a row, you need to do 2^x calculations. O(2^logn) = O(n)
If you have a tree that uses pointers, you're even worse off. Chasing a pointer under FHE has a cost O(y), where y is the size of your memory. Assuming y is proportional to n, that's O(n log n) just to look up a single key.
Citation needed. The argument isn't as simple as you made it look.
It's true that if the information needed for a computation is only stored in one location or the other of a random access memory according to a branch, accessing it will reveal which branch is taken, which is revealing too much.
But that isn't the only way to store information. For example a secret linear map or polynomial encoding of the information in a random access memory distributes the contents in such a way that you can sample multiple points to access encoded values, without obviously revealing the addressing scheme.
The server may or may not find those decoded parts meaningful: Meaningful would be something like console output while the computation progresses, and a "finished" signal. Non-meaningful (but still useful to the FHE program) would be something that looks like a sequence of memory requests whose locations may as well be pseudo-random.
[0] shows that o(N) lookups are impossible in general with only O(N) space in any private information retrieval scheme. That admittedly doesn't show that O(log n) lookups are impossible, but it's a similar result.
The improvements I'm aware of include (1) storing some extra information, (2) splitting the query into multiple phases to move the bulk of the Ω(N) cost out of the hot path, and (3) reframing the problem (an actual database lookup can't be improved, but similar constructions might still satisfy the end goal, or if you're using a hashmap as a sub-component then the composite algorithm might still be made efficient by never computing those expensive intermediates).
[0] https://link.springer.com/content/pdf/10.1007/s00145-004-013...
They're both enormous roadblocks. They're both key.
Even if you could do a 64 bit calculation every 0.25 nanoseconds, basic algorithms becoming O(n^2) or O(n^3) will cripple what you can compute.
And even if you could use the most efficient algorithms in the world, when your CPU is a billion times slower than normal you can't do much.
the real holy grail is program obfuscation, which lets you build your programs as "black boxes," containing secrets but never divulging them. there's progress on that front, but it's less feasible than FHE (which is saying something!)
1) Is my understanding correct - FHE-C++ library allows me to encrypt a photo from the client (in the browser), send it to the server, perform image operations on it, return back the photo to the client in a transformed state without the server ever being able to see what its transforming?
2) Is the holy grail you're noting allows any piece of software to be compiled and encrypted, but still take inputs and produce outputs? do the inputs and outputs have to be encrypted with the same key as the compiled software?
2. for obfuscation, the inputs and outputs are unencrypted, but the behavior of the software can't be analyzed. as a motivating example, say that I've built some ransomware, but I can't trust my C&C server to stay up. instead, I have the worm embed the private key into a freshly-compiled black box. if you feed the black box a valid Bitcoin block containing a ransom transaction to my address, it spits out the private key and you can decrypt your files.
there are many less evil examples out there - wanting to protect your ML models but still make them redistributable, etc.
How is this possible (I have no clue about FHE)? If the server can do operations on the image, then the image can't look like random noise, or not? And if there are indeed patterns the server can operate on, then the image can be decrypted?
A blur or sharpen filter would be an easy example. The server sees you take the random noise of each pixel, mix it with the nearby pixels, and output new random noise.
Which means the pixel positions are known to the server, which means the image isn't really encrypted?
The server would know that you're doing a blur, but it would have no idea what the contents of the image are.
Your data is encrypted. Your program is not encrypted.
If you want to hide your program, then things will get much slower yet again.
FHE is precisely the magic that allows doing operations on encrypted data and get encrypted results that you can then decrypt to valid end result.
except if you're mixing data sources.
for instance, say that I have a sweet Snapchat filter that I don't want to let off my servers. and you want to use my filter, but you don't want me to see your face in plaintext. in that case you can send me your encrypted photo, I run it through my filter, and send the results to you for you to decrypt.
its only real use case is that type of split data custody.
Indeed.
> the real holy grail is program obfuscation
Why so? FHE is a way stronger fundamental improvement that enables a completely different way to compute on individual data without compromising privacy and secrecy, in a trustless way that TEEs/SGX can't.
1. decrypt the inputs using its embedded private key.
2. do the computation.
3. encrypt the outputs and return them.
I'm not saying SGX is the holy grail, it's as compromised as Intel. I'm saying that an actual cryptographic primitive, like SGX but actually trustless and made of math instead of hardware, is.
unfortunately VBB was shown to be impossible, but indistinguishability obfuscation - producing a program that's indistinguishable from any other program that produces the same outputs for the same inputs - is possible, as recently demonstrated.
iO is weaker but still useful. imagine that I have a program that looks like "return input == secret". with iO, you couldn't recover the value of "secret" from the program, since "return Hash(input) == HashedSecret" is equivalent to the original, and iO guarantees that all alternate implementations of a function are indistinguishable.
I do not want the people who are running the program to know my input. I do not want the program to know my input. Does indistinguishability obfuscation help with that?
if you want the output to be encrypted too (even potentially with a different key), you can use vanilla FHE.
Does this exist, even in theory?
0. https://github.com/joeltg/brainfreeze
edit: actually, that's the fatal flaw with FHEs as Turing machines. you can't ever tell when they halt, because that would require decrypting a bit and exposing it to the end user. you just have to keep running them until you get bored, or abandon Turing machines for circuits.
A great article on IO: https://www.quantamagazine.org/computer-scientists-achieve-c...
I'm not sure whether you could successfully hide the FHE decryption key with iO, though.
- "Variable-length arrays are not supported"
- "While-loops and for-loops with a variable end-condition are not supported."
- "Floating-point data types are not supported."
"Even greater"! Wow!
Even greater than what?
With FHE, if the server runs FHE software then you can encrypt your data with your secret key without ever disclosing it to the server (as it does not need it to compute stuff on your data).
The benefits are many: the server never has to know anything about your data (imagine a MedTech company doing diagnosis, your medical data will be safe from their prying eyes).
If the server is compromised, the attacker cannot look at your data, potentially no more private information leak!
On the regulatory side you potentially don't have to worry about GDPR anymore, you can't access the data of your users.
Edit: Thinking of it more, I could imagine some sort of image transformations (e.g. a blur filter) as applications - but those are fairly corner use cases, are there more broad ones?
FHE lets you work on the data and update it without ever revealing the contents.
I think you only need homomorphic encryption if the transformation is something that the owner of data can't or shouldn't do themselves. It would be overkill for simple financial information.
For example, running machine learning models on homomorphically encrypted health data.
Image filtering made me think of this FHE demo/quickstart: https://6min.zama.ai/
As per conditional programs, there might be a way to do it but it would always be the worst case (no early loop break for example) so the runtimes would be aweful and the memory state could get prohibitively large I guess (to keep track of all the branches).
Indeed there are. FHE could provide a way to stay compliant with privacy regulations while outsourcing processing to external providers.
Think medical data or trade secrets.
Google/Bing/DuckDuckGo either return nothing or return nothing related for Booleanifier.
https://crypto.stackexchange.com/questions/3555/homomorphic-...
That's also related to why blind signatures work, but also to why RSA padding is necessary (to intentionally break this property!).
https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_sign...
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...
I guess blind signatures may also helpful for this intuition.
Helps to demystify the voodoo :)