New Techniques for Private Stream Searching
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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 Om 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 Om. Our technique requires some metadata to be returned in addition to the documents for this we present a scheme with Om logtm 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 Om overall communication and storage complexity with near optimal constant factors. The previous best scheme for private stream searching was shown to have Om log m communication and storage complexity. In applications where tm m, we may revert to an alternative method of returning the necessary metadata which has Om log m 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.
- Information Science