TY - GEN
T1 - Order-preserving symmetric encryption
AU - Boldyreva, Alexandra
AU - Chenette, Nathan
AU - Lee, Younho
AU - O'Neill, Adam
PY - 2009
Y1 - 2009
N2 - 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 orderpreserving 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.
AB - 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 orderpreserving 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.
UR - http://www.scopus.com/inward/record.url?scp=67650690965&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-01001-9_13
DO - 10.1007/978-3-642-01001-9_13
M3 - Conference contribution
AN - SCOPUS:67650690965
SN - 3642010008
SN - 9783642010002
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 224
EP - 241
BT - Advances in Cryptology - EUROCRYPT 2009 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
T2 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009
Y2 - 26 April 2009 through 30 April 2009
ER -