Order-Preserving Symmetric Encryption.

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 chosenplaintext 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. ∗School of Computer Science, Georgia Institute of Technology, 266 Ferst Drive, Atlanta, GA 30332, USA. E-mail: [e-mail]. †Department of Mathematical Sciences, Clemson University, O-110 Martin Hall, Box 340975, Clemson, SC 29634, USA. E-mail: [e-mail]. Most of the work done while at the Georgia Institute of Technology. ‡Department of Information and Communication Engineering Yeungnam University, Republic of Korea. E-mail: [e-mail]. Work done while at the Georgia Institute of Technology. §Department of Computer Science, Boston University, 111 Cummington St., Boston, MA 02215, USA. E-mail: [e-mail]. Work done while at the Georgia Institute of Technology and University of Texas.