Order preserving encryption for numeric data

TLDR

Encryption protects sensitive data but prevents efficient querying beyond exact matches. The authors propose an order‑preserving encryption scheme for numeric data that enables direct comparison operations on ciphertexts. The scheme supports graceful updates, allows new values to be added without re‑encrypting existing data, supports standard database indexes, integrates with existing systems, and is designed for environments where attackers have access to the encrypted database but lack prior domain knowledge. The scheme delivers sound and complete query results and remains robust against value estimation attacks in such environments.

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.