International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
David Cash
Cong Zhang
Download:
DOI: 10.1007/978-3-030-03810-6_6
Search ePrint
Search Google
Conference: TCC 2018
Abstract: We consider a 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 they differ. While their work could achieve order-revealing encryption with short ciphertexts that expand the plaintext by a factor $$\approx 1.58$$, it could only find order-preserving encryption with longer ciphertexts 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.
BibTeX
@inproceedings{tcc-2018-29032,
  title={A Ciphertext-Size Lower Bound for Order-Preserving Encryption with Limited Leakage},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  publisher={Springer},
  volume={11240},
  pages={159-176},
  doi={10.1007/978-3-030-03810-6_6},
  author={David Cash and Cong Zhang},
  year=2018
}