Described is a system for secure database searching. The system comprises a client-server architecture which allows a client to securely search a database of records possessed by a server. A database query is generated by the client and transmitted to the server. The database query is processed by the server using a privacy-preserving search protocol. An encrypted match result is produced by the server without decrypting the database query. The encrypted match result is sent to the client, and the client decrypts the encrypted match result to obtain a set of block identifiers representing blocks of records in the database that match the database query. The client obtains a block of encrypted records containing match results using only the set of block identifiers. The match results are decrypted by the client using a key obtained from the server. The unencrypted match results to the database query are then output.