Multi-Dimensional Range Query over Encrypted Data

TLDR

The authors design MRQED to address privacy concerns in sharing network audit logs and other applications. MRQED encrypts flow summaries at the gateway, permits auditors to decrypt flows within specified attribute ranges via a released key, and is formally proven secure under bilinear assumptions while demonstrating practical performance on audit logs. MRQED preserves privacy of irrelevant flows, supports diverse applications such as financial and medical audit logs, and enables privacy‑preserving stock trading through its dual problem solution.

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 privacypreserving manner.