4 ms·

> 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

> 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.
hansvm 5y ago
> Citation needed. [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-0134-y.pdf https://link.springer.com/content/pdf/10.1007/s00145-004-013...

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.

hansvm 5y ago

> Citation needed. [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-0134-y.pdf https://link.springer.com/content/pdf/10.1007/s00145-004-013...