[Dmbu-l] Order-Preserving Encryption [Thursday 04/19 @ 12:00 pm in MCS 148]

Charalampos Mavroforakis cmav at bu.edu
Tue Apr 17 22:35:21 EDT 2012

Hello everyone.

Adam O'Neill will be our speaker for this Thursday 4/19, 12pm in MCS 148

*Data Mining and Database Group Seminar*

*Order-Preserving Encryption*
*Speaker: *Adam O'Neill,* *Boston University

We will provide an overview of our recent results (with A. Boldyreva, N.
Chenette, and Y. Lee) on order-preserving encryption (OPE), a type of
symmetric encryption on numerical data that preserves plaintext order.
 This property is in particular useful to do highly efficient range
query processing
on an encrypted database without needing to decrypt.  We will first discuss
a natural security notion for OPE that we show is unfortunately
*unachievable* by any practical OPE scheme.  We will then go on to propose
a different security notion in the style of pseudorandom-function-**security,
asking that the OPE is ``as random as possible'' subject to the
order-preserving constraint, which we call POPF (pseudorandom
order-preserving function) security.  We will then show how to construct an
efficient, POPF-secure OPE scheme based on a blockcipher and a sampling
algorithm for the hypergeometic distribution.  For the remainder of the
talk, we turn to the question of what encryption via a POPF-secure OPE
scheme leaks about the underlying data.  In  articular, we will explain
that, for a database of randomly distributed plaintexts and appropriate
choice of parameters, POPF-secure OPE leaks neither the precise value of
any  laintext nor the precise distance between any two of them. On the
other hand, such encryption leaks approximate value of any plaintext as well
as approximate distance between any two plaintexts, each to an accuracy of
about square root of the domain size.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20120417/dc3f66d1/attachment.html 

More information about the Dmbu-l mailing list