What if you have: 1) The database server in the data warehouse, with no keys. 2) A small privileged server under your control with both keys 3) Users with the public key

When adding an entry, the request goes through the privileged server. It then adds the item to the database, encrypted with the public key. It also updates a table of contents, encrypted with the private key.

Public key holders can read the table of contents, but cannot read the database.

Private key users can read the database, and already know the table of contents.

The private key does not reside on the foreign database server, only on a small stateless proxy server which you fully control.

It would probably work better if you just had a really strong "any" encryption and the proxy server for doing writes. Plus the table of contents that anybody with a login can read straight from the database.