Full Database Reconstruction in Two Dimensions
Full Database Reconstruction in Two Dimensions
复制标题
DOI：
10.1145/3372297.3417275
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Francesca Falzon;Evangelia Anna Markatou;Akshima;David Cash;A. Rivkin;J. Stern;R. Tamassia
中科院分区：
文献类型：
--
作者：
Francesca Falzon;Evangelia Anna Markatou;Akshima;David Cash;A. Rivkin;J. Stern;R. Tamassia
在过去的几年里，我们看到了多起针对支持范围查询的一维数据库的攻击。这些攻击通过利用访问模式泄漏以及已知的查询分布或搜索模式泄漏来实现完整的数据库重建。我们是第一个超越一个维度，从两个维度探索这一威胁的人。我们通过证明可能存在指数数量的不同数据库产生等效泄漏来揭示重建攻击的内在局限性。接下来，我们提出一个完整的数据库重建攻击。我们的算法在多项式时间内运行，并返回与给定泄漏曲线一致的所有数据库的多尺寸编码。我们实现我们的算法并观察现实世界的数据库，这些数据库承认大量等效数据库，这与我们的理论结果一致。
In the past few years, we have seen multiple attacks on one-dimensional databases that support range queries. These attacks achieve full database reconstruction by exploiting access pattern leakage along with known query distribution or search pattern leakage. We are the first to go beyond one dimension, exploring this threat in two dimensions. We unveil an intrinsic limitation of reconstruction attacks by showing that there can be an exponential number of distinct databases that produce equivalent leakage. Next, we present a full database reconstruction attack. Our algorithm runs in polynomial time and returns a poly-size encoding of all databases consistent with the given leakage profile. We implement our algorithm and observe real-world databases that admit a large number of equivalent databases, which aligns with our theoretical results.