Abstract
Many media watermarking techniques require the use of a secret key
to detect/decode the watermark in/from the marked object. Court proofs of
ownership are strongly related to the ability of the rights holder (i.e.
Alice) to convince a judge (i.e. Jared) or a jury of the safety of the
encoding/decoding key in the frame of the considered watermarking algorithm.
Multimedia Watermarking algorithms operate often in high bandwidth, noisy
domains, that empower defendant (i.e. evil Mallory) court time claims of
exhaustive key-space searches for matching keys. In other words, Mallory's
position claims that Alice cannot prove her associated rights over the
disputed content as the actual data domain in case allowed her to "try"
different keys until one of them made the watermark magically "appear" in
the (allegedly) un-marked object.
Watermarking algorithms in general and in the media framework in particular,
would thus benefit from an intrinsic component of the security assessment
step, namely a solution offering the ability to fight exactly such claims.
One mechanism for securing this ability is to precommit to the watermarking
key, at any time {\em before} watermark embedding. Precommitting to secrets
in the framework of watermarking presents a whole new set of challenges,
derived from the particularities of the domain.
The main contribution of this paper is to define the main problem behind it
and offer a solution to key precommitment in watermarking, solution augmented
by a practical, illustrative example of an actual key precommitment method.
Given any watermarking scheme our solution increases its ability to "convince"
that the associated watermark is not embedded through some post-facto
matching key choice (or even fortuitously), and was in fact deliberately
inserted.
In some sense we are providing a mechanism for the "amplification
of convinceability" of any watermarking algorithm. That is, if
the watermarked object makes it to court then its watermark proof
is dramatically more convincing, and in particular immune to claims
of matching key searches.
Thus, we introduce the main motivation behind precommitment to keys
in the process of watermarking and present an algorithm for key
precommitment, analyzing its integration as part of any existing
watermarking application.
Our solution, while relying on new (e.g. tolerant hashing) and existing
concepts (e.g. key-space size reduction, watermark randomization)
ties them together to produce a drastic (i.e. to virtually 0) reduction
of the probability of success in the case of random key-space searches
for matching keys, thus making a convincing counter-point to claims as
the one above.
We analyze trade-offs and present some alternative ideas for key
precommitment. We discuss properties of the presented scheme as well as
some other envisioned solutions.
