Secure kNN computation on encrypted databases

TLDR

Cloud‑service providers such as Google and Amazon are expanding into SaaS, turning their vast infrastructure into platforms that host business applications, yet conventional encryption that promises unbreakable protection often fails to support database queries on encrypted data. This work addresses the need to protect data in cloud‑based SaaS platforms by formulating the problem of secure computation on encrypted databases and introducing the SCONEDB model that captures execution and security requirements. The authors focus on k‑nearest neighbor queries, introduce an asymmetric scalar‑product‑preserving encryption (ASPE) scheme, and build two secure kNN protocols that resist attacks under varying adversarial knowledge while differing in overhead, with extensive performance evaluations demonstrating their efficiency. The two proposed kNN protocols, built on ASPE, successfully resist practical attacks at distinct adversarial knowledge levels while offering different overhead trade‑offs.

Abstract

Service providers like Google and Amazon are moving into the SaaS (Software as a Service) business. They turn their huge infrastructure into a cloud-computing environment and aggressively recruit businesses to run applications on their platforms. To enforce security and privacy on such a service model, we need to protect the data running on the platform. Unfortunately, traditional encryption methods that aim at providing "unbreakable" protection are often not adequate because they do not support the execution of applications such as database queries on the encrypted data. In this paper we discuss the general problem of secure computation on an encrypted database and propose a SCONEDB Secure Computation ON an Encrypted DataBase) model, which captures the execution and security requirements. As a case study, we focus on the problem of k-nearest neighbor (kNN) computation on an encrypted database. We develop a new asymmetric scalar-product-preserving encryption (ASPE) that preserves a special type of scalar product. We use APSE to construct two secure schemes that support kNN computation on encrypted data; each of these schemes is shown to resist practical attacks of a different background knowledge level, at a different overhead cost. Extensive performance studies are carried out to evaluate the overhead and the efficiency of the schemes.