Cryptology ePrint Archive: Report 2012/624
Order-Preserving Symmetric Encryption
Alexandra Boldyreva and Nathan Chenette and 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.
Category / Keywords: secret-key cryptography / Searchable encryption, symmetric encryption, range queries, cloud storage
Publication Info: Eurocrypt 2009
Date: received 4 Nov 2012
Contact author: sasha at gatech edu
Available formats: PDF | BibTeX Citation
Version: 20121105:135015 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]