Paper 2012/624

Order-Preserving Symmetric Encryption

Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O’Neill

Abstract

We initiate the cryptographic study of order-preserving symmetric encryption (OPE), a primitive suggested in the database community by Agrawal et al.~(SIGMOD '04) for allowing efficient range queries on encrypted data. Interestingly, we first show that a straightforward relaxation of standard security notions for encryption such as indistinguishability against chosen-plaintext attack (IND-CPA) is unachievable by a practical OPE scheme. Instead, we propose a security notion in the spirit of pseudorandom functions (PRFs) and related primitives asking that an OPE scheme look ``as-random-as-possible" subject to the order-preserving constraint. We then design an efficient OPE scheme and prove its security under our notion based on pseudorandomness of an underlying blockcipher. Our construction is based on a natural relation we uncover between a random order-preserving function and the hypergeometric probability distribution. In particular, it makes black-box use of an efficient sampling algorithm for the latter.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Eurocrypt 2009
Keywords
Searchable encryptionsymmetric encryptionrange queriescloud storage
Contact author(s)
sasha @ gatech edu
History
2012-11-05: received
Short URL
https://ia.cr/2012/624
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/624,
      author = {Alexandra Boldyreva and Nathan Chenette and Younho Lee and Adam O’Neill},
      title = {Order-Preserving Symmetric Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/624},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/624}},
      url = {https://eprint.iacr.org/2012/624}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.