16 ms·

> 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.
        Dylan16807 5y ago
        I follow the idea that revealing the physical location is safe under a method like this. But how does the program tell the server which physical locations to grab? The knowledge of which locations are needed is inside the encryption.
        jlokier 5y ago
        Ah. By using more complex FHE states and operations, such that part of the state can be decoded/decrypted by the server to direct the server's actions, while other parts remain opaque. 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.
  - 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.

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.
        Dylan16807 5y ago
        I follow the idea that revealing the physical location is safe under a method like this. But how does the program tell the server which physical locations to grab? The knowledge of which locations are needed is inside the encryption.
        jlokier 5y ago
        Ah. By using more complex FHE states and operations, such that part of the state can be decoded/decrypted by the server to direct the server's actions, while other parts remain opaque. 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.
- 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.