Order-Preserving Encryption for Numeric Data

Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu

Original Abstract: Encryption is a well established technology for protecting sensitive data. However, once encrypted, data can no longer be easily queried aside from exact matches. We present an order-preserving encryption scheme for numeric data that allows any comparison operation to be directly applied on encrypted data. Query results produced are sound (no false hits) and complete (no false drops). Our scheme handles updates gracefully and new values can be added without requiring changes in the encryption of other values. It allows standard database indexes to be built over encrypted tables and can easily be integrated with existing database systems. The proposed scheme has been designed to be deployed in application environments in which the intruder can get access to the encrypted database, but does not have prior domain information such as the distribution of values and cannot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.


Rakesh Agrawal is a Microsoft Technical Fellow and heads the Search Labs in Microsoft Research.  He is the recipient of the ACM-SIGKDD First Innovation Award, ACM-SIGMOD Edgar F. Codd Innovations Award, ACM-SIGMOD Test of Time Award, VLDB 10-Yr Most Influential Paper Award, ICDE Most Influential Paper Award, and  Computerworld First Horizon Award. He is a Member of the National Academy of Engineering, a Fellow of ACM, and a Fellow of IEEE. Scientific American named him to the list of 50 top scientists and technologists in 2003.
Jerry Kiernan has been working on advanced database research and development at IBM since 1991. He received his Ph.D. from the University of Paris and INRIA in 1989.  His focus areas have included the optimization of ETL workflows for generating data marts, database privacy and security, XML queries and views of relational tables, database object-relational extensions, and object-oriented database middleware. He has published numerous papers on these and other database topics in leading conferences and journals. Some recent contributions include new analytics for summarizing large event logs using machine learning techniques; database access control incorporating notions of privacy for data subjects; database disclosure auditing using advanced algorithms based on query logs and temporal database extensions; data matching algorithms for tracking the sources of compromised relational tables, database watermarking techniques for establishing ownership of data. He is currently working on database tooling for heterogeneous database environments, and automated deployment of database software for public and private clouds.
Ramakrishnan Srikant is a Distinguished Research Scientist at Google. His research interests include user models, internet monetization, and data mining.
Yirong Xu is the CEO and founder of Meilishuo.com, the largest online marketplace on women fashion and beauty in China, with more than 60 million monthly active users. Its investors include Sequoia and Tencent. He is dreaming to interrupt the fashion commerce in China by leveraging mobile and data technologies. Prior, he founded the most popular RSS reader in China. Before that, he worked at IBM Almaden Research Center on data management and data mining technologies. Xu obtained his B.S. in Peking University and M.S. in Stanford University, both in Computer Science.