Order preserving encryption for numeric data

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 databse 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 annot encrypt or decrypt arbitrary values of his choice. The encryption is robust against estimation of the true value in such environments.

REFERENCES

• 1: R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Hippocratic databses. In Proc. of the 28th Int'l Conference on Very Large Databases, Hong Kong, China, August 2002.
• 2: Niv Ahituv , Yeheskel Lapid , Seev Neumann, Processing encrypted data, Communications of the ACM, v.30 n.9, p.777-780, Sept. 1987 [doi>10.1145/30401.30404]
• 3: G. Bebek. Anti-tamper database research: Inference control techniques. Technical Report EECS 433 Final Report, Case Western Reserve University, November 2002.
• 4: L. Bouganim and P. Pucheral. Chip-secured data access: Confidential data on untrusted servers. In 28th Int'l Conference on Very Large Databses, pages 131--142, Hong Kong, China, August 2002.
• 5: Zbigniew J. Czech , George Havas , Bohdan S. Majewski, An optimal algorithm for generating minimal perfect hash functions, Information Processing Letters, v.43 n.5, p.257-264, Oct. 5, 1992 [doi>10.1016/0020-0190(92)90220-P]
• 6: Ernesto Damiani , S. De Capitani Vimercati , Sushil Jajodia , Stefano Paraboschi , Pierangela Samarati, Balancing confidentiality and efficiency in untrusted relational DBMSs, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948124]
• 7: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 8: J. Domingo-Ferrer and J. Herrera-Joancomarti. A privacy homomorphism allowing field operations on encrypted data. I Jornades de Matematica Discreta i Algorismica, Universitat Politecnica de Catalunya, March 1998.
• 9: Josep Domingo i Ferrer, A new privacy homomorphism and applications, Information Processing Letters, v.60 n.5, p.277-282, Dec. 9, 1996 [doi>10.1016/S0020-0190(96)00170-6]
• 10: J. Feigenbaum, M. Y. Liberman, and R. N. Wright. Cryptographic protection of databases and software. In Proc. of the DIMACS Workshop on Distributed Computing and Cryptography, 1990.
• 11: Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991 [doi>10.1145/125187.125200]
• 12: S. C. Gultekin Ozsoyoglu, David Singer. Anti-tamper databases: Querying encrypted databases. In Proc. of the 17th Annual IFIP WG 11.3 Working Conference on Database and Applications Security, Estes Park, Colorado, August 2003.
• 13: 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]
• 14: T. Hamilton. Error sends bank files to eBay. The Toronto Star, September 15, 2003.
• 15: Y. E. Ioannidis. The history of histograms (abridged). In Proc. of 29th Int'l Conf. on Very Large Data Bases (VLDB), Berlin, Germany, September 2003.
• 16: Arnd Christian König , Gerhard Weikum, Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.423-434, September 07-10, 1999
• 17: Manish Mehta , Rakesh Agrawal , Jorma Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.18-32, March 25-29, 1996
• 18: Oracle Corporation. Database Encryption in Oracle 8i, August 2000.
• 19: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 20: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 21: R. L. Rivest, L. Adelman, and M. L. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, pages 169--178, 1978.
• 22: B. Schneier. Applied Cryptography. John Wiley, second edition, 1996.
• 23: Dawn Xiaodong Song , David Wagner , Adrian Perrig, Practical Techniques for Searches on Encrypted Data, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.44, May 14-17, 2000
• 24: Douglas Stinson, Cryptography: Theory and Practice,Second Edition, CRC/C&H, 2002
• 25: R. Vingralek, Gnatdb: A small-footprint, secure database system. In 28th Int'l Conference on Very Large Databases, pages 884--893, Hong Kong, China, August 2002.