  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.
