Practical Techniques for Search on Encrypted Data

Dawn Song

UC Berkeley

Joint work with David Wagner and Adrian Perrig.

It is desirable to store data on data storage servers such as mail servers and file servers in encrypted form to reduce security and privacy risks. But this usually implies that one has to sacrifice functionality for security. For example, if a client wishes to retrieve only documents containing certain words, it was not previously known how to let the data storage server perform the search and answer the query without loss of data confidentiality.

We have designed a cryptographic schemes for the problem of searching on encrypted data and provide proofs of security for the resulting crypto systems. Our scheme is provable secure and do not reveal any more information than the search result. Server does not know the real query word and cannot perform any arbitrary unauthorized queries as its wish. Our scheme is also simple, fast (for a document of length n, the encryption and search algorithms only need O(n) stream cipher and block cipher operations), and introduce almost no space and communication overhead, and hence are practical to use today.

Gates 4B, 11/28/00, 4:15 PM