Not sure if its implemented exactly like this but one could imagine that the server must use the client's public key to encrypt the database into a blob it can't decrypt. The encrypted input is used to read the encrypted blob in a way the server can't understand to construct a result the server cannot understand. The result blob is sent to the client which can decrypt it.
