Look up private information retrieval (PIR) and oblivious RAM (ORAM). EDIT: This particular bit from the announcement "but we're pushing query logic and decryption keys client-side" seems to point to ORAM.

I was recently reading a number of ORAM papers, considering to implement something as a side-project to play a bit with modern C++. The overhead is significant, but practical, i.e., far less than homomorphic encryption.