Abstract | ||
---|---|---|
We initiate the cryptographic study of order-preserving symmetric encryption (OPE), a prim- itive suggested in the database community by Agrawal et al. (SIGMOD '04) for allowing ecient range queries on encrypted data. Interestingly, we rst 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 ecient 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 ecient sampling algorithm for the latter. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-01001-9_13 | IACR Cryptology ePrint Archive |
Keywords | Field | DocType |
security notion,ope scheme look,efficient sampling algorithm,standard security notion,order-preserving constraint,efficient range query,practical ope scheme,random order-preserving function,order-preserving symmetric encryption,efficient ope scheme,symmetric encryption,probability distribution,range query,it security | Symmetric-key algorithm,Discrete mathematics,Cryptography,Pseudorandomness,Computer science,Theoretical computer science,Encryption,40-bit encryption,Probabilistic encryption,Database encryption,Pseudorandom number generator | Journal |
Volume | ISSN | Citations |
2012 | 0302-9743 | 312 |
PageRank | References | Authors |
10.49 | 31 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alexandra Boldyreva | 1 | 2297 | 114.80 |
Nathan Chenette | 2 | 531 | 17.37 |
Younho Lee | 3 | 405 | 25.13 |
Adam O’Neill | 4 | 358 | 11.58 |