IACR News item: 18 November 2015
Daniel Roche, Daniel Apon, Seung Geol Choi, Arkady Yerukhimovich
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.