3 ms·
This capability is not exactly Fully Homomorphic Encryption (FHE). In the cryptographic literature this is typically referred to as PIR, or Private Information
by ngneer 4y ago
This capability is not exactly Fully Homomorphic Encryption (FHE). In the cryptographic literature this is typically referred to as PIR, or Private Information Retrieval [https://en.wikipedia.org/wiki/Private_information_retrieval https://en.wikipedia.org/wiki/Private_information_retrieval]. Counterintuitive indeed. The idea is not totally new, though...
- blintz 4y agoTrue! We are using FHE to perform PIR. The underlying scheme we use is a real homomorphic encryption scheme (Regev + GSW), but yeah, we explicitly do not support performing arbitrary computation on encrypted data. As it turns out, that's still quite slow - the Google FHE C++ transpiler still takes seconds to do 32-bit arithmetic operations. Our PIR system is able to achieve much more practical speed + communication overheads.
- ngneer 4y agoI vaguely recall basic PIR schemes turn a database from O(n) to O(n^2). While this would be transparent to users of the service, could you comment on space overhead?
- blintz 4y agoThe space overhead is roughly constant (or at most logarithmic in n), and varies by the scheme. In practice, it’s something like 1.5-8x overhead. This is no big deal for storage, but does make it a pain on the memory side for processing (since the full database, including the overhead factor, needs to be resident in memory).
- ngneer 4y agoAwesome, thanks for taking the time to elucidate!
- Oreko 4y agoI haven't read their protocol, but you can easily implement PIR using FHE through polynomial evaluation.