8 ms·

This seems pretty revolutionary, if indeed arbitrary C++ programs can be written as FHE. Are there any key limitations?

entire-name 5y ago
It has a dependency on XLS[cc], so they share their limitations: https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler#limitations https://github.com/google/fully-homomorphic-encryption/tree/...
BelenusMordred 5y ago
> Are there any key limitations? It's slow, you would not want any part of your program that isn't security critical using it.
- R0b0t1 5y ago
  This may not always be true.
  - hansvm 5y ago
    Slowness is necessary to some degree. Early stopping leaks information, so FHE algorithms wind up being worst-case for all inputs (e.g., O(N) to find the value for a key).
    - DaiPlusPlus 5y ago
      I think `O(log n)` for key-lookup, assuming fully-indexed data, should be sufficient, as that's the worst-case lookup time in a balanced tree. 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.
      - Dylan16807 5y ago
        O(log n) lookups are impossible under FHE. 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.
        jlokier 5y ago
        > O(log n) lookups are impossible under FHE. 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.
        Dylan16807 5y ago
        You would have to decrypt part of your data to tell the host what memory locations to fetch. Is that still FHE? And how would you do it safely?
        jlokier 5y ago
        Yes, it's still FHE, because the physical locations (e.g. RAM addresses, disk block indexes) don't reveal which logical index (in the FHE encrypted array) you are looking up. The encrypted data isn't just shuffled in memory with a secret permutation, it's encoded in a way that's analogous to a hologram but with cryptographic operations.
        5y ago
    - PeterisP 5y ago
      The key part of slowness is not the algorithms, but inherent speed of processing information this way. E.g. the TFHE library used here (https://tfhe.github.io/tfhe/ https://tfhe.github.io/tfhe/) claims that "Each binary gate takes about 13 milliseconds single-core time to evaluate", and it operates on individual bits (so things like integer multiplication need many such 13ms operations), so doing something relatively trivial on non-tiny data sizes - like iterating over a megabyte of data to do something that's O(n) anyway - takes an impractical amount of time.
      - Dylan16807 5y ago
        > The key part of slowness is not the algorithms, but inherent speed of processing information this way. 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.
sterlind 5y ago
FHE isn't obfuscation, nor is it functional encryption. it's not the cryptographic equivalent of Intel SGX; all it lets you do is put encrypted inputs into a program and get encrypted outputs back. 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!)
- systemvoltage 5y ago
  Could you please explain a bit more to the more uninitiated like me: 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?
  - sterlind 5y ago
    1. yes, exactly. 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.
    - bildung 5y ago
      > 1. yes, exactly. 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?
mikeiz404 5y ago
See https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler#limitations https://github.com/google/fully-homomorphic-encryption/tree/... - "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."
MichaelMoser123 5y ago
the term homomorphism implies that the transformations on the encrypted data (such as addition and multiplication) also apply on the plain text; now you can't check if a value is zero, as it's a different value in the plaintext and encrypted text; so you can't branch or do any decission, based on the value of the encrypted data (i think that would severely limit the practical utility of this trick)
- PeterisP 5y ago
  This has some similarities to how you do 'vectorization' of data processing to avoid branching; you can "make decisions" with conditional expressions (y = condition ? a : b ) implemented as y = condition * a + (!condition) * b. You do have to calculate both branches, but you get the conditional result depending on that decision.
IceTDrinker 5y ago
I saw some answers but one potential roadblock is runtime, it looks like google transpiler generates a boolean circuit, which is kind of like emulating a small piece of hardware in software

It has a dependency on XLS[cc], so they share their limitations: https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler#limitations https://github.com/google/fully-homomorphic-encryption/tree/...

BelenusMordred 5y ago

> Are there any key limitations? It's slow, you would not want any part of your program that isn't security critical using it.

R0b0t1 5y ago
This may not always be true.
- hansvm 5y ago
  Slowness is necessary to some degree. Early stopping leaks information, so FHE algorithms wind up being worst-case for all inputs (e.g., O(N) to find the value for a key).
  - DaiPlusPlus 5y ago
    I think `O(log n)` for key-lookup, assuming fully-indexed data, should be sufficient, as that's the worst-case lookup time in a balanced tree. 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.
    - Dylan16807 5y ago
      O(log n) lookups are impossible under FHE. 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.
      - jlokier 5y ago
        > O(log n) lookups are impossible under FHE. 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.
        Dylan16807 5y ago
        You would have to decrypt part of your data to tell the host what memory locations to fetch. Is that still FHE? And how would you do it safely?
        jlokier 5y ago
        Yes, it's still FHE, because the physical locations (e.g. RAM addresses, disk block indexes) don't reveal which logical index (in the FHE encrypted array) you are looking up. The encrypted data isn't just shuffled in memory with a secret permutation, it's encoded in a way that's analogous to a hologram but with cryptographic operations.
        5y ago
  - PeterisP 5y ago
    The key part of slowness is not the algorithms, but inherent speed of processing information this way. E.g. the TFHE library used here (https://tfhe.github.io/tfhe/ https://tfhe.github.io/tfhe/) claims that "Each binary gate takes about 13 milliseconds single-core time to evaluate", and it operates on individual bits (so things like integer multiplication need many such 13ms operations), so doing something relatively trivial on non-tiny data sizes - like iterating over a megabyte of data to do something that's O(n) anyway - takes an impractical amount of time.
    - Dylan16807 5y ago
      > The key part of slowness is not the algorithms, but inherent speed of processing information this way. 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.

sterlind 5y ago

FHE isn't obfuscation, nor is it functional encryption. it's not the cryptographic equivalent of Intel SGX; all it lets you do is put encrypted inputs into a program and get encrypted outputs back. 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!)

systemvoltage 5y ago
Could you please explain a bit more to the more uninitiated like me: 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?
- sterlind 5y ago
  1. yes, exactly. 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.
  - bildung 5y ago
    > 1. yes, exactly. 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?

mikeiz404 5y ago

See https://github.com/google/fully-homomorphic-encryption/tree/main/transpiler#limitations https://github.com/google/fully-homomorphic-encryption/tree/... - "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."

MichaelMoser123 5y ago

the term homomorphism implies that the transformations on the encrypted data (such as addition and multiplication) also apply on the plain text; now you can't check if a value is zero, as it's a different value in the plaintext and encrypted text; so you can't branch or do any decission, based on the value of the encrypted data (i think that would severely limit the practical utility of this trick)

PeterisP 5y ago
This has some similarities to how you do 'vectorization' of data processing to avoid branching; you can "make decisions" with conditional expressions (y = condition ? a : b ) implemented as y = condition * a + (!condition) * b. You do have to calculate both branches, but you get the conditional result depending on that decision.

IceTDrinker 5y ago

I saw some answers but one potential roadblock is runtime, it looks like google transpiler generates a boolean circuit, which is kind of like emulating a small piece of hardware in software