Efficient and Secure Top-k Queries With Top Order-Preserving Encryption

Abstract

Top-k queries can retrieve the most relevant tuples from massive datasets and have wide implementations, such as PageRank, healthcare analytics, and decision making. The increasing demands of outsourcing large datasets to public clouds with privacy concern expect new techniques to securely perform top-k queries on encrypted data on the cloud servers. Order-preserving encryption (OPE) can be used for answering top-k queries correctly and naturally. However, it is over qualified since it unnecessarily leaks too much information (i.e., orders of non-top-k values). In this paper, we propose a mutable top OPE (TOPE) to first enable top-1 (min or max) queries on encrypted data with minimized information leakage. Then, we extend this TOPE to support top-k queries in general. With TOPE, the ciphertexts of top-k values are still the top-k in the ciphertext domain, while the ciphertexts of non-top-k values are in meaningless order. In addition, we rigorously define and prove the security of TOPE with indistinguishability under top-ordered chosen-plaintext attacks. We implement our scheme on synthetic and real datasets to show its effectiveness and efficiency. The search performance of top-k queries on massive TOPE ciphertexts with our scheme is almost as fast as on the plaintexts.