Paper 2016/786

What Else is Revealed by Order-Revealing Encryption?

F. Betül Durak, Thomas M. DuBuisson, and David Cash

Abstract

The security of order-revealing encryption (ORE) has been unclear since its invention. Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions. This work shows that more plaintext information can be extracted from ORE ciphertexts than was previously thought. We identify two issues: First, we show that when multiple columns of correlated data are encrypted with ORE, attacks can use the encrypted columns together to reveal more information than prior attacks could extract from the columns individually. Second, we apply known attacks, and develop new attacks, to show that the \emph{leakage} of concrete ORE schemes on non-uniform data leads to more accurate plaintext recovery than is suggested by the security theorems which only dealt with uniform inputs.

Note: Added a citation to concurrent and independent work by Grubbs et al.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. ACM CCS 2016
DOI
10.1145/2976749.2978379
Keywords
order-revealing encryptionorder-preserving encryptiondatabase encryption
Contact author(s)
david cash @ cs rutgers edu
History
2016-09-07: revised
2016-08-18: received
See all versions
Short URL
https://ia.cr/2016/786
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/786,
      author = {F.  Betül Durak and Thomas M.  DuBuisson and David Cash},
      title = {What Else is Revealed by Order-Revealing Encryption?},
      howpublished = {Cryptology ePrint Archive, Paper 2016/786},
      year = {2016},
      doi = {10.1145/2976749.2978379},
      note = {\url{https://eprint.iacr.org/2016/786}},
      url = {https://eprint.iacr.org/2016/786}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.