Reconstructing with Even Less

Abstract

Leakage-abuse attacks using access pattern leakage from range queries have been shown to reconstruct encrypted databases. However, prior work is either restricted to one-dimensional databases or requires access to all possible responses in two-dimensions. In this paper, we explore what an adversary can achieve with minimal leakage, focusing on denser databases, and present a leakage abuse attack from access pattern of range queries in multiple dimensions. Our attack employs a novel technique to systematically amplify access pattern leakage, inferring a large number of new query responses that have not been requested by the user. Letm be the size of the database domain. Our attack works on d-dimensional databases and achieves approximate reconstruction. For dense databases and a parameter 0 < ? < 1, our attack fully reconstructs an inner portion of size ?m of the database (referred to as the ?-core) after observing O(m logm) queries, uniformly at random. These are significant improvements over previous attacks that require the full set of responses, which has size O(m²). We are the first to leverage graph drawing techniques for database reconstruction attacks. We implement our attack and evaluate it with experiments on real-world databases, achieving accurate reconstructions after observing a small percentage of the responses.