Databases Reference
In-Depth Information
appears then in multiple (statistically significant number of) different tuples.
This is possible only if
A
is not a primary key but rather another categorical
attribute, with repeating duplicate values.
The authors propose a set of solutions to this issue, including composing
the actual watermark encoding out of a combination of several different sub-
encodings, each in turn using a different
k
1
value. Each such sub-encoding will
ignore all tuples with previously seen values of the attribute
A
(in the fitness
criteria). While each of these “low impact” encodings would be weaker than
the original solution, their combined “sum” can be made arbitrarily strong,
by increasing their number. At the same time correlation attacks would be
defeated, as each of the encodings would use a different key thus making such
attacks impossible “across” the encodings.
The authors further discuss additional extensions and properties of the
solution, including the following.
•
Consumer-Driven Design: The solution features a consumer-driven design.
Each property of the database that needs to be preserved is written as
a constraint on the allowable change to the dataset. The watermarking
algorithm is then applied with these constraints as input and re-evaluates
them continuously for each alteration. A backtrack log is kept to allow
undo operations in case certain constraints are violated by the current
watermarking step.
•
Incremental Updatability: The solution supports incremental updates nat-
urally. As updates occur to the data, the resulting tuples can be evaluated
on the fly for “fitness” and watermarked accordingly.
•
Blind Watermarking: The method does not require the availability of the
un-watermarked data at detection time.
•
Minimizing Alteration Distance: An interesting problem to consider is the
case when, for a given “fit” tuple, certain alterations would be preferred
to others (e.g., changing “Chicago, O'Hare” into “Chicago” is preferred to
“Las Vegas”). The authors propose to handle this scenario by a modified
encoding procedure that naturally accommodates and minimizes such an
“alteration distance” metric.
•
Extreme Vertical Partitioning: To counter extreme vertical partitioning
attacks in which only a single attribute
A
is preserved in the result, the
authors propose to encode a watermark in one of the only remaining char-
acteristic properties, namely the value occurrence frequency distribution
for each possible value of
A
. To do so a scheme of watermarking for numeric
sets [30] can be applied in this “frequency” domain.
•
Multi-Layer Self-Reinforcing Watermarks: To counter the scenario where
Mallory gains knowledge, e.g., during a court hearing, of a multiply-used
encoding key, the authors propose to embed multiple (i) weak watermarks
with different secret keys and reveal in court only a certain subset of these,
or (ii)
self-re-enforcing
pairs of watermarks (
w
1
,w
2
)
i
with different keys
