16-05-2012, 05:19 PM
Privacy-Preserving Updates to Anonymous and Confidential Databases
Secure_Computing_Privacy-Preserving_Updates_to_Anonymous_and_Confidential_Databases.pdf (Size: 510.99 KB / Downloads: 54)
INTRODUCTION
It is today well understood that databases represent an
important asset for many applications and thus their
security is crucial. Data confidentiality is particularly
relevant because of the value, often not only monetary,
that data have. For example, medical data collected by
following the history of patients over several years may
represent an invaluable asset that needs to be adequately
protected. Such a requirement has motivated a large
variety of approaches aiming at better protecting data
confidentiality and data ownership. Relevant approaches
include query processing techniques for encrypted data
and data watermarking techniques. Data confidentiality
is not however the only requirement that needs to be
addressed.
Problem Statement
Figure 1 captures the main participating parties in our
application domain. We assume that the information
concerning a single patient (or data provider) is stored
in a single tuple, and DB is kept confidentially at the
server. The users in Figure 1 can be treated as medical
researchers who have the access to DB. Since DB is
anonymous, the data provider’s privacy is protected
from these researchers. (Note that to follow the traditional
convention, in Section 4 and later sections, we use
Bob and Alice to represent the data provider and the
server respectively.)
RELATED WORK
A preliminary approach to this problem was investigated
in [33]. However these protocols have some serious
limitations, in that they do not support generalizationbased
updates, which is the main strategy adopted for
data anonymization. Therefore, if the database is not
anonymous with respect to a tuple to be inserted, the
insertion cannot be performed. In addition one of the
protocols is extremely inefficient. In the current paper,
we present two efficient protocols, one of which also
support the private update of a generalization-based
anonymous database. We also provide security proofs
and experimental results for both protocols. So far no
experimental results had been reported concerning such
type of protocols; our results show that both protocols
perform very efficiently. In what follows, we briefly
address other research directions relevant for our work.
The first research direction deals with algorithms
for database anonymization.
BASIC DEFINITIONS AND PRIMITIVES
Anonymity Definitions
We consider a table T = ft1; : : : ; tng over the attribute set
A. The idea is to form subsets of indistinguishable tuples
by masking the values of some well-chosen attributes. In
particular, when using a suppression-based anonymization
method, we mask with the special value , the value
deployed by Alice for the anonymization. When using a
generalization-based anonymization method, original values
are replaced by more general ones, according to
apriori established value generalization hierarchies (VGHs)
[32]. We adopt the following notations thereafter: