I spent a long time trying to build a privacy-preserving database. The challenge is that a persistent attacker (a honest, but curious server hosting your data)

I spent a long time trying to build a privacy-preserving database. The challenge is that a persistent attacker (a honest, but curious server hosting your data) can defeat the encryption by observing the access pattern. This happens because issuing the same query twice will access the same encrypted data, and the same amount of encrypted data. Naively one would think that this is of no use, and such patterns can be trivially obfuscated, but any statistical correlation can be fatal, and ensuing that they do not occur is costly. If you would download the entire database for each query that would be private, but also have a linear communication overhead. You could rewrite data to a new location after you read it, which is what ORAM does, and it has at least a logarithmic communication overhead. This is where the buck stops, logarithmic is a theoretical minimum cost even for the weakest computational access pattern privacy guarantees. With differential privacy guarantees a double logarithmic overhead is possible, but it is not clear when such guarantees are useful. Fully homomorphic encryption would only allow to push the overhead from communication to computation. On the practical side there are symmetric searchable encryption schemes with forward and backward privacy. They are reasonably functional, with reasonable leakage, without any guarantees. They tend to be vulnerable to sophisticated adversaries with knowledge about the queries or the documents. These schemes often have to deal with more than just access pattern privacy, because they not all passive (where the server is only a storage device, the client selects the documents to access). They have to worry about the search tokens presented to the server, which is now running code. Some of these schemes have to deal with a malicious server breaking protocol.