Security issues in querying encrypted data

There has been considerable interest in querying encrypted data, allowing a \secure database server " model where the server does not know data values. This paper shows how results from cryptography prove the impossibility of developing a server that meets cryptographic-style denitions of security and is still ecient enough to be practi-cal. The weaker denitions of security supported by previous secure database server proposals have the potential to reveal signicant in-formation. We propose a denition of a secure database server that provides probabilistic security guarantees, and sketch how a practi-cal system meeting the denition could be built and proven secure. The primary goal of this paper is to provide a vision of how research in this area should proceed: ecient encrypted database and query processing with provable security properties.