Query on the cloud: improved privacy-preserving k-nearest neighbor classification over the outsourced database

In the current cloud computing and big data era, outsourcing the storage and associated query operations of large-scale databases to cloud service providers has become an increasingly popular computing paradigm. However, due to the potential mutual distrust among the data owner (DO), cloud server (CS) and query user (QU), the risk of privacy disclosure constrains the wide deployment of this attractive computing paradigm. To handle this dilemma, various encryption approaches are designed to assure privacy during query processing over outsourced databases. Recently, Wu et al. (World Wide Web 22(1), 101-123 2019) presented a 'secure' k-nearest neighbor (kNN) classification scheme over encrypted cloud database which aimed to concurrently keep the privacy of the database, the DO's key, the QU's query, and the data access patterns. In this paper, we first revisit their scheme and present an efficient known-plaintext attack on the privacy of database with linearization technique. Then, we propose an improved scheme that outperforms the prior scheme in both security and efficiency. Precisely, on the security side, we realize the above four security intentions with rigorous theoretical arguments. On the efficiency side, our new design greatly reduces the computational overhead of the DO and the QU, and makes full use of the resources of two cloud servers by better balancing their computational loads. Finally, we measure the practical performance of our scheme from an experimental perspective, and the result corroborates our theoretical analysis.

Automated summary

This paper introduces encryption methods for privacy protection in cloud databases and improves the security and efficiency through an improved algorithm.