Cryptology ePrint Archive: Report 2018/953

A Comparative Evaluation of Order-Preserving and Order-Revealing Schemes and Protocols

Dmytro Bogatov and George Kollios and Leo Reyzin

Abstract: Database query evaluation over encrypted data has received a lot of attention recently. Order Preserving Encryption (OPE) and Order Revealing Encryption (ORE) are two important encryption schemes that have been proposed in this area. These schemes can provide very efficient query execution but at the same time may leak some information to adversaries. In this paper, we present the first comprehensive comparison among a number of important OPE and ORE schemes using a framework that we developed. We evaluate protocols that are based on these schemes as well. We analyze and compare them both theoretically and experimentally and measure their performance over database indexing and query evaluation techniques using not only execution time but also {\IO} performance and usage of cryptographic primitive operations. Our comparison reveals some interesting insights concerning the relative security and performance of these approaches in database settings. Furthermore, we propose a number of improvements for some of these scheme and protocols. Finally, we provide a number of suggestions and recommendations that can be valuable to database researchers and users.

Category / Keywords: implementation / ORE, OPE, searchable encryption, range queries, databases

Date: received 5 Oct 2018

Contact author: dmytro at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20181009:160437 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]