International Association
for Cryptologic Research

Recently there has been much interest in performing database queries over encrypted data to enable functionality while protecting sensitive data. One particularly efficient mechanism for executing such queries is order-preserving encryption/encoding (OPE) which results in ciphertexts that preserve the relative order of the underlying plaintexts thus allowing range and comparison queries to be performed directly over the ciphertext. In particular, Popa et al. (S&P 2013) recently gave the first interactive, mutable order-preserving encoding scheme achieving the strongest possible security for OPE while allowing for efficient range queries. However, this construction requires the bulk of the work to be performed when inserting data into the database, something that is not desirable for the high insertion rates of today\'s big data databases.

In this paper, we propose an alternative approach to range queries over encrypted data that is optimized for efficient insert while still maintaining search functionality. Specifically, we propose a new primitive called partial order preserving encoding (POPE) that achieves ideal OPE security while providing extremely fast insertion and efficient (amortized) search. Our scheme is better suited to today\'s insert-heavy database scenarios. For example, with about one million insertions and one thousand range queries, our POPE scheme is 20X faster than the scheme by Popa et al.

We also propose a new form of frequency-hiding security for POPE, as recently studied by Kerschbaum (CCS 2015) for OPE, and show how to extend our scheme to satisfy it.