Paper 2018/521

Ciphertext Expansion in Limited-Leakage Order-Preserving Encryption: A Tight Computational Lower Bound

Gil Segev and Ido Shahaf

Abstract

Order-preserving encryption emerged as a key ingredient underlying the security of practical database management systems. Boldyreva et al. (EUROCRYPT '09) initiated the study of its security by introducing two natural notions of security. They proved that their first notion, a ``best-possible'' relaxation of semantic security allowing ciphertexts to reveal the ordering of their corresponding plaintexts, is not realizable. Later on Boldyreva et al. (CRYPTO '11) proved that any scheme satisfying their second notion, indistinguishability from a random order-preserving function, leaks about half of the bits of a random plaintext. This unsettling state of affairs was recently changed by Chenette et al. (FSE '16), who relaxed the above ``best-possible'' notion and constructed a scheme satisfying it based on any pseudorandom function. In addition to revealing the ordering of any two encrypted plaintexts, ciphertexts in their scheme reveal only the position of the most significant bit on which the plaintexts differ. A significant drawback of their scheme, however, is its substantial ciphertext expansion: Encrypting plaintexts of length $m$ bits results in ciphertexts of length $m \cdot \ell$ bits, where $\ell$ determines the level of security (e.g., $\ell = 80$ in practice). In this work we prove a lower bound on the ciphertext expansion of any order-preserving encryption scheme satisfying the ``limited-leakage'' notion of Chenette et al. with respect to non-uniform polynomial-time adversaries, matching the ciphertext expansion of their scheme up to lower-order terms. This improves a recent result of Cash and Zhang (ePrint '17), who proved such a lower bound for schemes satisfying this notion with respect to computationally-unbounded adversaries (capturing, for example, schemes whose security can be proved in the random-oracle model without relying on cryptographic assumptions). Our lower bound applies, in particular, to schemes whose security is proved in the standard model.

Note: Small corrections

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2018
Contact author(s)
ido shahaf @ cs huji ac il
History
2018-09-25: last of 2 revisions
2018-06-04: received
See all versions
Short URL
https://ia.cr/2018/521
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/521,
      author = {Gil Segev and Ido Shahaf},
      title = {Ciphertext Expansion in Limited-Leakage Order-Preserving Encryption: A Tight Computational Lower Bound},
      howpublished = {Cryptology ePrint Archive, Paper 2018/521},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/521}},
      url = {https://eprint.iacr.org/2018/521}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.