Secure kNN computation on encrypted databases

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.

REFERENCES

• 1: Rakesh Agrawal , Dmitri Asonov , Murat Kantarcioglu , Yaping Li, Sovereign Joins, Proceedings of the 22nd International Conference on Data Engineering, p.26, April 03-07, 2006 [doi>10.1109/ICDE.2006.144]
• 2: Rakesh Agrawal , Jerry Kiernan , Ramakrishnan Srikant , Yirong Xu, Order preserving encryption for numeric data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007632]
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 4: A. Asuncion and D. Newman. UCI Machine Learning Repository, 2007.
• 5: Hans Delfs , Helmut Knebl, Introduction to cryptography: principles and applications, Springer-Verlag New York, Inc., New York, NY, 002
• 6: Alexandre Evfimievski , Ramakrishnan Srikant , Rakesh Agrawal , Johannes Gehrke, Privacy preserving mining of association rules, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775080]
• 7: Gartner. Assessing the Security Risks of Cloud Computing (ID Number: G00157782), 2008.
• 8: Bugra Gedik , Ling Liu, Location Privacy in Mobile Systems: A Personalized Anonymization Model, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.620-629, June 06-10, 2005 [doi>10.1109/ICDCS.2005.48]
• 9: Gabriel Ghinita , Panos Kalnis , Ali Khoshgozaran , Cyrus Shahabi , Kian-Lee Tan, Private queries in location based services: anonymizers are not necessary, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376631]
• 10: Hakan Hacigümüş , Bala Iyer , Chen Li , Sharad Mehrotra, Executing SQL over encrypted data in the database-service-provider model, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564717]
• 11: H. Hacigumus, B. Iyer, and S. Mehrotra. Efficient execution of aggregation queries over encrypted relational databases. In DASFAA, 2004.
• 12: H. Hacigumus, S. Mehrotra, and B. Iyer. Providing database as a service. In ICDE, 2002.
• 13: A. Khoshgozaran and C. Shahabi. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In SSTD, 2007.
• 14: N. Li, T. Li, and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In ICDE, 2007.
• 15: K. Liu, C. Giannella, and H. Kargupta. An attacker's view of distance preserving maps for privacy preserving data mining. In PKDD, 2006.
• 16: Ashwin Machanavajjhala , Johannes Gehrke , Daniel Kifer , Muthuramakrishnan Venkitasubramaniam, \ell -Diversity: Privacy Beyond \kappa -Anonymity, Proceedings of the 22nd International Conference on Data Engineering, p.24, April 03-07, 2006 [doi>10.1109/ICDE.2006.1]
• 17: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 18: Einar Mykletun , Gene Tsudik, Incorporating a Secure Coprocessor in the Database-as-a-Service Model, Proceedings of the Innovative Architecture on Future Generation High-Performance Processors and Systems, p.38-44, January 17-19, 2005 [doi>10.1109/IWIA.2005.28]
• 19: E. Mykletun and G. Tsudik. Aggregation queries in the database-as-a-service model. In ESORICS, 2006.
• 20: S. R. M. Oliveira and O. R. Zaiane. Privacy preserving clustering by data transformation. In SBBD, Manaus, Amazonas, Brazil, 2003.
• 21: Latanya Sweeney, k-anonymity: a model for protecting privacy, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, v.10 n.5, p.557-570, October 2002 [doi>10.1142/S0218488502001648]
• 22: Dong Xin , Jiawei Han , Kevin C. Chang, Progressive and selective merge: computing top-k with ad-hoc ranking functions, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247494]
• 23: Dong Xin , Jiawei Han , Hong Cheng , Xiaolei Li, Answering top-k queries with multi-dimensional selections: the ranking cube approach, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 24: Lei Zou , Lei Chen, Dominant Graph: An Efficient Indexing Structure to Answer Top-K Queries, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.536-545, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497462]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Security, integrity, and protection

General Terms:
Algorithms, Security

Keywords:
encryption, knn, security