SPEAKER: Elaine Shi

TIME: Wednesday 12-1pm, April 11, 2007

PLACE: NSH 1507

TITLE: Multi-Dimensional Range Query over Encrypted Data

ABSTRACT:
We design an encryption scheme called Multi-dimensional Range Query over
Encrypted Data (MRQED), to address the privacy concerns related to the
sharing of network audit logs and various other applications. Our scheme
allows a network gateway to encrypt summaries of network flows before
submitting them to an untrusted repository. When network intrusions are
suspected, an authority can release a key to an auditor, allowing the
auditor to decrypt flows whose attributes (e.g., source and destination
addresses, port numbers, etc.) fall within specific ranges. However, the
privacy of all irrelevant flows are still preserved. We formally define
the security for MRQED and prove the security of our construction under
the decision bilinear Diffie-Hellman and decision linear assumptions in
certain bilinear groups. We study the practical performance of our construction
in the context of network audit logs. Apart from network audit logs, our
scheme also has interesting applications for financial audit logs, medical
privacy, untrusted remote storage, etc. In particular, we show that MRQED
implies a solution to its dual problem, which enables investors to trade
stocks through a broker in a privacy-preserving manner.

Joint work with John Bethencourt, T-H. Hubert Chan, Dawn Song, and Adrian Perrig.