This seems pretty revolutionary, if indeed arbitrary C++ programs can be written as FHE. Are there any key limitations?
- "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."
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.
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.