Order-preserving symmetric encryption
Speaker: Alexandra Boldyrev , GeorgiaTech
Date: April 10 2009
Time: 10:30AM to 12:00PM
Location: 32-G449
Contact: Be, 3-6098, imbe@mit.edu
We initiate the cryptographic study of order-preserving symmetric
encryption (OPE), a primitive suggested in the database community for
allowing efficient range queries on encrypted data. We first show
that a straightforward relaxation of standard security notions for
encryption such as indistinguishability against chosen-plaintext
attack is unachievable by a practical OPE scheme. Instead, we propose
a security notion in the spirit of pseudorandom functions 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.
This is joint work with Nate Chenette, Adam O'Neill and Younho Lee.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in April 2009
