Verifiable and private top-k monitoring

In a data streaming model, records or documents are pushed from a data owner, via untrusted third-party servers, to a large number of users with matching interests. The match in interest is calculated from the correlation between each pair of document and user query. For scalability and availability reasons, this calculation is delegated to the servers, which gives rise to the need to protect the privacy of the documents and user queries. In addition, the users need to guard against the eventuality of a server distorting the correlation score of the documents to manipulate which documents are highlighted to certain users. In this paper, we address the aforementioned privacy and verifiability challenges. We introduce the first cryptographic scheme which concurrently safeguards the privacy of the documents and user queries in such a data streaming model, while enabling users to verify the correlation scores obtained. We provide techniques to bound the computation demand in decrypting the correlation scores, and we demonstrate the overall practicality of the scheme through experiments with real data.