Paper 2018/953

A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols

Dmytro Bogatov, George Kollios, and Leonid Reyzin

Abstract

Database query evaluation over encrypted data can allow database users to maintain the privacy of their data while outsourcing data processing. Order-Preserving Encryption (OPE) and Order-Revealing Encryption (ORE) were designed to enable efficient query execution, but provide only partial privacy. More private protocols, based on Searchable Symmetric Encryption (SSE), Oblivious RAM (ORAM) or custom encrypted data structures, have also been designed. In this paper, we develop a framework to provide the first comprehensive comparison among a number of range query protocols that ensure varying levels of privacy of user data. We evaluate five ORE-based and five generic range query protocols. We analyze and compare them both theoretically and experimentally and measure their performance over database indexing and query evaluation. We report not only execution time but also I/O performance, communication amount, and usage of cryptographic primitive operations. Our comparison reveals some interesting insights concerning the relative security and performance of these approaches in database settings.

Note: This is a revised version submitted to VLDB 2019.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. PVLDB 2019
DOI
10.14778/3324301.3324309
Keywords
Range query protocolsOREOPEsearchable encryptiondatabases
Contact author(s)
dmytro @ bu edu
History
2019-06-20: last of 3 revisions
2018-10-09: received
See all versions
Short URL
https://ia.cr/2018/953
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2018/953,
      author = {Dmytro Bogatov and George Kollios and Leonid Reyzin},
      title = {A Comparative Evaluation of Order-Revealing Encryption Schemes and Secure Range-Query Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2018/953},
      year = {2018},
      doi = {10.14778/3324301.3324309},
      note = {\url{https://eprint.iacr.org/2018/953}},
      url = {https://eprint.iacr.org/2018/953}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.