Paper 2017/1120

A Ciphertext-Size Lower Bound for Order-Preserving Encryption with Limited Leakage

David Cash and Cong Zhang

Abstract

We consider a recent security definition of Chenette, Lewi, Weis, and Wu for order-revealing encryption (ORE) and order-preserving encryption (OPE) (FSE 2016). Their definition says that the comparison of two ciphertexts should only leak the index of the most significant bit on which the differ. While their work could achieve ORE with short ciphertexts that expand the plaintext by a factor approximate 1.58, it could only find OPE with longer ciphertxts that expanded the plaintext by a security-parameter factor. We give evidence that this gap between ORE and OPE is inherent, by proving that any OPE meeting the information-theoretic version of their security definition (for instance, in the random oracle model) must have ciphertext length close to that of their constructions. We extend our result to identify an abstract security property of any OPE that will result in the same lower bound.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Symmetric EncryptionSearchable EncryptionLower Bound
Contact author(s)
congresearch @ gmail com
History
2017-11-24: received
Short URL
https://ia.cr/2017/1120
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1120,
      author = {David Cash and Cong Zhang},
      title = {A Ciphertext-Size Lower Bound for Order-Preserving Encryption with Limited Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1120},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1120}},
      url = {https://eprint.iacr.org/2017/1120}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.