Files

Abstract

When outsourcing data, one of the things the host learns about the data is the number of records returned in response to each user query. We refer to this as volume leakage and study attacks on databases that leak the volumes of range queries over database attributes. We provide two new attacks within this area, one against noisy volume leakage and another against volume leakage of $d$-dimensional databases for $d>1$ (where previously work only considered the case of $d=1$). To build these attack algorithms, we prove the equivalence of this problem to the turnpike problem. We then take ideas from algorithms previously used to solve the turnpike problem and expand upon them to yield our attacks. This connection also allows us to directly apply numerous theoretical results from the turnpike problem to the problem of database reconstruction from volume leakage. Further, we prove several new theoretical results with respect to the database reconstruction problem using ideas from the turnpike literature. In order to address the issue of determining uniqueness of some reconstruction of a database from volume leakage, we are forced to take a step back and study the mathematical foundations of the problem. We do this by reducing the problem of database reconstruction to that of tiling finite multisets with a tile of fixed size. Unfortunately, many of the questions we asked with respect to multisets were still open, even with respect to sets of contiguous elements. Thus, we start by proving structural results about the properties of tilings of finite intervals of integers and prove upper and lower bounds on the number of such tilings. In an initial effort to generalize these tiling results and work towards our desired database reconstruction results, we generalize our tiling results in two major ways. The first is to generalize them to tilings of $d$-dimensional finite sets. The second is to generalize them to certain families of non-contiguous finite sets. We hope that further generalizations of our latter results will yield an algorithm for efficiently determining uniqueness of a database reconstruction attack's output.

Details

Actions

PDF

from
to
Export
Download Full History