A system for private stream searching, introduce by Ostrovsky and Skeith, allows a client to provide an untrusted server with an encrypted search query. A system for private stream searching, introduced by Ostrovsky and Skeith, allows a client to provide an untrusted server with an encrypted search query. The server uses the query on a stream of documents and returns the matching documents to the client while learning nothing about the nature of the query. We present a new scheme for conducting private keyword search on streaming data which requires O(m) server to client communication complexity to return the content of the matching documents, where m is the size of the documents. The required storage on the server conducting the search is also O(m). Our technique requires some metadata to be returned in addition to the documents; for this we present a scheme with O(m log(t/m)) communication and storage complexity. In many streaming applications, the number of matching documents is expected to be a fixed fraction of the stream length; in this case the new scheme has the optimal O(m) overall communication and storage complexity with near optimal constant factors. The previous best scheme for private stream searching was shown to have O(m log m) communication and storage complexity. In applications where t/m > m, we may revert to an alternative method of returning the necessary metadata which has O(mlogm) communication and storage complexity; in this case constant factor improvements over the previous scheme are achieved. Our solution employs a novel construction in which the user reconstructs the matching files by solving a system of linear equations. This allows the matching documents to be stored in a compact buffer rather than relying on redundancies to avoid collisions in the storage buffer as in previous work. We also present a unique encrypted Bloom filter construction which is used to encode the set of matching documents. In this paper we describe our scheme, prove it secure, analyze its asymptotic performance, and describe several extensions.

26 pages

*SRI International

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]