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.

I 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?

The 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).

Awesome, thanks for taking the time to elucidate!

I haven't read their protocol, but you can easily implement PIR using FHE through polynomial evaluation.