Databases Reference
In-Depth Information
2.4 Data Access Privacy
In existing protocols, even though data sets are stored in encrypted form on
the server, the
client query access patterns
leak essential information about
the data. A simple attack can correlate known public information with
hot
data items (i.e., with high access rates), effectively compromising their confi-
dential nature. In competing business scenarios, such leaks can be extremely
damaging, particularly due to their unpredictable nature.
This is why, to protect confidentiality, it is important to also provide as-
surances of access pattern privacy. No existing work has tackled this problem
yet for relational frameworks. It is thus essential to explore query protocols
that leak minimal information about the currently executing query. Access
patterns to data tuples become less meaningful when access semantics are un-
known to the server. For example the binary predicate join method proposed
above does not require the server to know the actual join predicates. Achieving
such goals for
arbitrary
relational queries will be a challenging proposition in
today's query processors, potentially requiring fundamental changes in base
query processing.
To achieve these goals we first turn to existing research.
Private Informa-
tion Retrieval
(PIR) protocols were first proposed as a theoretical primitive
for accessing individual items of outsourced data, while preventing servers to
learn anything about the client's access patterns [47]. Chor et al. [48] proved
that in information theoretic settings in which queries do not reveal any infor-
mation about the accessed data items, a solution requires
Ω
(
n
) bits of com-
munication. To avoid this overhead, they show that for multiple
non-colluding
databases holding replicated copies of the data, PIR schemes exist that re-
quire only sub-linear communication overheads. This multi-server assumption
however, is rarely viable in practice.
In single-server settings, it is known that PIR requires a full transfer of
the database [47, 49] for computationally unbounded servers. For bounded
adversaries however,
computational
PIR (cPIR) mechanisms have been pro-
posed [40, 41, 45, 86, 87, 93, 96, 122]. In such settings however, it is trivial to
establish an
O
(
n
) lower bound on server processing, mandating expensive
trapdoor operations per bit, to achieve access privacy. This creates a signif-
icant privacy - eciency trade-off between the required server computation
cycles and the time to actually transfer the data and perform the query at
the client site.
We explore this trade-off in [118] where we discuss single-server com-
putational PIR
for the purpose of preserving client access patterns leakage
.
We show that deployment of non-trivial single server private information re-
trieval protocols on real (Turing) hardware is orders of magnitude more time-
consuming than trivially transferring the entire database to the client. The
deployment of computational PIR in fact
increases
both overall execution
time, and the probability of
forward
leakage, when the deployed present trap-
