Reconstructing with Even Less: Amplifying Leakage and Drawing Graphs

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. Let 𝑚 be the size of the database domain. Our attack works on 𝑑-dimensional databases and achieves approximate reconstruction. For dense databases and a parameter 0 < 𝜆 < 1, our attack fully reconstructs an inner portion of size 𝜆𝑚 of the database (referred to as the 𝜆-core) after observing 𝑂 (𝑚 log 𝑚) queries, uniformly at random. These are significant improvements over previous attacks that require the full set of responses, which has size 𝑂 (𝑚 2 ). 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.

• Security and privacy → Cryptanalysis and other attacks; Database and storage security.