Data inference from encrypted databases: A multi-dimensional order-preserving matching approach

Yanjun Pan, Alon Efrat, Ming Li, Boyang Wang, Hanyu Quan, Joseph Mitchell, Jie Gao, Esther Arkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Due to increasing concerns of data privacy, databases are being encrypted before they are stored on an untrusted server. To enable search operations on the encrypted data, searchable encryption techniques have been proposed. Representative schemes use order-preserving encryption (OPE) for supporting efficient Boolean queries on encrypted databases. Yet, recent works showed the possibility of inferring plaintext data from OPE-encrypted databases, merely using the order-preserving constraints, or combined with an auxiliary plaintext dataset with similar frequency distribution. So far, the effectiveness of such attacks is limited to single-dimensional dense data (most values from the domain are encrypted), but it remains challenging to achieve it on high-dimensional datasets (e.g., spatial data), which are often sparse in nature. In this paper, for the first time, we study data inference attacks on multi-dimensional encrypted databases (with 2-D as a special case). We formulate it as a 2-D order-preserving matching problem and explore both unweighted and weighted cases, where the former maximizes the number of points matched using only order information and the latter further considers points with similar frequencies. We prove that the problem is NP-hard, and then propose a greedy algorithm, along with a polynomial-time algorithm with approximation guarantees. Experimental results on synthetic and real-world datasets show that the data recovery rate is significantly enhanced compared with the previous 1-D matching algorithm.

Original languageEnglish (US)
Title of host publicationMobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PublisherAssociation for Computing Machinery
Pages151-160
Number of pages10
ISBN (Electronic)9781450380157
DOIs
StatePublished - Oct 11 2020
Event21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020 - Virtual, Online, United States
Duration: Oct 11 2020Oct 14 2020

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

Conference21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020
Country/TerritoryUnited States
CityVirtual, Online
Period10/11/2010/14/20

Keywords

  • data inference
  • encrypted database
  • multi-dimensional matching
  • order-preserving encryption

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'Data inference from encrypted databases: A multi-dimensional order-preserving matching approach'. Together they form a unique fingerprint.

Cite this