3 ms·
True! 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 suppor
by blintz 4y ago
True! 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!