Secure kNN computation on encrypted databases
Authors:
Open Access
- 29 June 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 139-152
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 computa- tion 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. © 2009 ACM.link_to_OA_fulltexKeywords
This publication has 16 references indexed in Scilit:
- Private queries in location based services2008
- Dominant Graph: An Efficient Indexing Structure to Answer Top-K Queries2008
- Incorporating a Secure Coprocessor in the Database-as-a-Service Model2006
- Aggregation Queries in the Database-As-a-Service Model2006
- An Attacker’s View of Distance Preserving Maps for Privacy Preserving Data Mining2006
- Location Privacy in Mobile Systems: A Personalized Anonymization Model2005
- Providing database as a service2003
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002
- Privacy preserving mining of association rules2002
- Executing SQL over encrypted data in the database-service-provider model2002