Secure kNN computation on encrypted databases
Top Cited Papers
- 29 June 2009
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
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 servicesPublished by Association for Computing Machinery (ACM) ,2008
- Dominant Graph: An Efficient Indexing Structure to Answer Top-K QueriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Incorporating a Secure Coprocessor in the Database-as-a-Service ModelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Aggregation Queries in the Database-As-a-Service ModelLecture Notes in Computer Science, 2006
- An Attacker’s View of Distance Preserving Maps for Privacy Preserving Data MiningLecture Notes in Computer Science, 2006
- Location Privacy in Mobile Systems: A Personalized Anonymization ModelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Providing database as a servicePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACYInternational Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002
- Privacy preserving mining of association rulesPublished by Association for Computing Machinery (ACM) ,2002
- Executing SQL over encrypted data in the database-service-provider modelPublished by Association for Computing Machinery (ACM) ,2002