Databases Reference
In-Depth Information
in these values. Mallory could mount a statistical attack by correlating
marked bit values among tuples with the same most significant bits. This
issue has been also considered in [18] where a similar solution has been
adopted. This, is discussed in more detail elsewhere in this topic.
3.1 Multi-Bit Watermarks
While there likely exist applications whose requirements are satisfied by single-
bit watermarks, often it is desirable to provide for “relevance”, i.e., linking
the encoding to the rights holder identity. This is especially important if the
watermark aims to defeat against invertibility attacks (
A5
).
In a single-bit encoding this can not be easily achieved. Additionally, while
the main proposition of watermarking is not covert communication but rather
rights assessment, there could be scenarios where the actual message payload
is of importance.
One apparent direct extension from single-bit watermarks to a multi-bit
version would be to simply deploy a different encoding, with a separate water-
mark key, for each bit of the watermark to be embedded. This however, might
not be possible, as it will raise significant issues of inter-encoding interference:
the encoding of later bits will likely distort previous ones. This will also make
it harder to handle ulterior claim of rights attacks (
A4
).
In the following we discuss multi-bit watermark encodings. We briefly dis-
cuss a direct-domain encoding [19] that extends the work by Kiernan, Agrawal
et. al. [1, 16] and then explore a distribution-encoding method by Sion et.
al. [27, 29, 30, 32, 33] and [34].
Multi-Bit Direct Domain Encoding
In [19] Li et. al. extend the work by Kiernan, Agrawal et. al. [1,16] to provide
for multi-bit watermarks in a direct domain encoding. This is discussed in
extended detail elsewhere in this topic. Here we briefly summarize. The scheme
functions as follows. The database is parsed and, at each bit-encoding step, one
of the watermark bits is randomly chosen for embedding; the solution in [1,16]
is then deployed to encode the selected bit in the data at the “current” point.
The “strength of the robustness” of the scheme is claimed to be increased
with respect to [1, 16] due to the fact that the watermark now possesses an
additional dimension, namely length. This should guarantee a better upper
bound for the probability that a valid watermark is detected from unmarked
data, as well as for the probability that a fictitious secret key is discovered
from pirated data (i.e., invertibility attacks
A5
). This upper bound is said
to be independent of the size of database relations thus yielding robustness
against attacks that change the size of database relations.
