Databases Reference
In-Depth Information
bit zero) or greater than a larger threshold (for watermark bit one). Note that
some of the groups may not be watermarkable given user-specified change
tolerance. Also note that some redundant bits must be embedded such that
the original multi-bit watermark can be recovered in watermark detection
even if some of the encoded bits are destroyed in data attacks. Compared
with Li, Swarup, and Jajodia's multi-bit watermarking scheme, this scheme
is robust against linear transformation and does not depend on the existence
of a primary key. On the other hand, it incurs more watermarking overhead
as it requires ordering, grouping, and distribution-manipulating.
5.2 From Multiple Bit Watermark to Fingerprint
Li, Swarup, and Jajodia's multi-bit watermarking scheme can be easily ex-
tended to fingerprinting relational databases [17]. Fingerprinting is a different
class of information hiding techniques that insert digital marks into data with
the purpose of identifying the users who have been provided data, as oppose
to watermarking's purpose of identifying the sources of data. In fingerprinting,
the owner of the data embeds a user-specific mark into a data copy provided
to a user; he can subsequently detect the fingerprint in pirated data and use
it to identify the traitor who distributed the data.
Li, Swarup, and Jajodia's fingerprinting scheme is the same as their multi-
bit watermarking scheme except that the multi-bit watermark information
W
=(
w
0
,...,w
−
1
) is used to encode each user's identification information,
instead of the owner's. The watermark information is called fingerprint, as it
is used to distinguish among different users for traitor tracing.
Since different fingerprints are embedded into different data copies, it is
impossible to determine what the correct fingerprint is before fingerprint de-
tection. This is different from watermark detection, where the correct water-
mark is fixed and known. To solve this problem, two counters - one for bit
value zero, and one for bit value one - are maintained for each fingerprint
bit, recording the number of times that the fingerprint bit is recovered from
the data as to be either zero or one. At the end of fingerprint detection, the
fingerprint bit is set to be zero or one if the corresponding counter exceeds
τ
(in percentage) of the sum of the two counters for this bit; otherwise, the
fingerprint detection terminates with no traitor detected. If a binary string
is recovered at the end of fingerprint detection, it can be used to identify a
traitor (e.g., via the tracing algorithm proposed in [3]).
Since fingerprinting aims to identify a traitor, it can be subject to attacks
that cause an innocent principal (or no principal) to be identified as a traitor.
As a result, the false hit rate in fingerprinting can be further classified as
•
Misdiagnosis false hit: the probability of detecting a valid fingerprint from
data that has not been fingerprinted.
•
Misattribution false hit: the probability of detecting an incorrect but valid
fingerprint from fingerprinted data.
