Cryptology ePrint Archive: Report 2018/698

Parameter-Hiding Order Revealing Encryption

David Cash and Feng-Hao Liu and Adam O'Neill and Mark Zhandry and Cong Zhang

Abstract: Order-revealing encryption (ORE) is a popular primitive for outsourcing encrypted databases, as it allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.

Category / Keywords: secret-key cryptography / Order Revealing Encryption

Date: received 20 Jul 2018

Contact author: congresearch at gmail com, mzhandry@princeton edu, davidcash@cs uchicago edu, amoneill@gmail com, fenghao liu@fau edu

Available format(s): PDF | BibTeX Citation

Version: 20180724:033037 (All versions of this report)

Short URL: ia.cr/2018/698


[ Cryptology ePrint archive ]