Order Preserving Encryption for Numeric Data
Rakesh Agrawal Jerry Kiernan Ramakrishnan Srikant Yirong Xu
IBM Almaden Research Center
650 Harry Road, San Jose, CA 95120
ABSTRACT
Encryption is a well established technology for protecting sensi-
tive data. However, once encrypted, data can no longer be easily
queried aside from exact matches. We present an order-preserving
encryptionschemefor numeric data that allows any comparison op-
eration to be directly applied on encrypted data. Query results pro-
duced 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 al-
lows 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 val-
ues of his choice. The encryption is robust againstestimation of the
true value in such environments.
1. INTRODUCTION
Database systems typically offer access control as the means to
restrict access to sensitive data. This mechanism protects the pri-
vacyof sensitive information provided data is accessedusingthe in-
tended database system interfaces. However, access control, while
important and necessary, is often insufficient. Attacks upon com-
puter systems have shown that information can be compromised
if an unauthorized user simply gains access to the raw database
files, bypassing the database access control mechanism altogether.
For instance, a recent article published in the Toronto Star [14] de-
scribes an incident where a disk containing the records of several
hundred bank customers was being auctioned on eBay. The bank
had inadvertently sold the disk to the eBay re-seller as used equip-
ment without deleting its contents. Drawing upon privacy legisla-
tions and guidelinesworldwide, Hippocraticdatabasesalsoidentify
the protection of personal data from unauthorized acquisition as a
vital requirement [1].
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage, and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SIGMOD 2004 June 13-18, 2004, Paris, France.
Copyright 2004 ACM 1-58113-859-8/04/06
:::
$5.00.
Encryption is a well established technology for protecting sensi-
tive data [7] [22] [24]. Unfortunately, the integration of existing
encryption techniques with database systems causes undesirable
performance degradation. For example, if a column of a table con-
taining sensitive information is encrypted, and is used in a query
predicate with a comparison operator, an entire table scan would
be needed to evaluate the query. The reason is that the current en-
cryption techniques do not preserve order and therefore database
indices such as B-tree can no longer be used. Thus the query exe-
cution over encrypted databases can become unacceptably slow.
We presentan encryption techniquecalledOPES(Order Preserv-
ing Encryption Scheme) that allows comparison operations to be
directly applied on encrypteddata,without decrypting theoperands.
Thus, equality and range queries as well as the MAX, MIN, and
COUNT queries can be directly processed over encrypted data.
Similarly, GROUP BY and ORDER BY operations can also be ap-
plied. Only when applying SUM or AVG to a group do the values
need to be decrypted. OPES is also endowed with the following
properties:
The results of query processing over data encrypted using
OPES are exact. They neither contain any false positives nor
miss any answer tuple. This feature of OPES sharply differ-
entiates it from schemes such as [13] that produce a superset
of answer, necessitating filtering of extraneous tuples in a
rather expensive and complex post-processing step.
OPES handles updates gracefully. A value in a column can
be modified or a new value can be inserted in a column with-
out requiring changes in the encryption of other values.
OPES can easily be integrated with existing database sys-
tems as it has been designed to work with the existing index-
ing structures such as B-trees. The fact that the database is
encrypted can be made transparent to the applications.
Measurements from an implementation of OPES in DB2 show that
the time and space overhead of OPES are reasonable for it to be
deployed in real systems.
1.1 Estimation Exposure
The security of an encryption scheme is conventionally assessed
by analyzing whether an adversary can find the key used for en-
cryption. See [22] [24] for a categorization of different levels of
attacks against a cryptosystem.
When dealing with sensitive numeric data, an adversary does
not have to determine the exact data value
p
corresponding to an
