Keys - Disappearing Cryptography - page 238

to be a null string.)

2. Extract one bit from K i and encode it in C i .

constraints.
The watermark can be tested by repeating the process. Any skep-
tical inquirer can get

Repeat this for all n

from the creator and step through the pro-
cess, checking the bits at each point.
This approach can be used to protect complicated engineering
designs where the creator must solve a difficult problem. Chip de-
signers, for instance, often solve large NP-complete problems when
they choose how to lay out transistors. This technique allows them to
encode a watermark in the chip design that essentially says, “Copy-
right 2001 Bob Chiphead”.
The technique can be applied tomore general information-hiding
problems or watermarking problems, but it has limitations. The cre-
ator must have the ability to find solutions to difficult problems- so-
lutions that are difficult for the average person to aquire. The sim-
plest way to accomplish this is to create a large computer that is
barely able to find solutions to large, difficult problems. Only the
owner of the computer (or one of similar strength) would be able to
generate solutions. Ron Rivest and Silvio Micali discuss using a sim-
ilar solution to mint small tokens, Peppercoin .[Riv04]

K 0

12.4.3 Using Matrix Multiplication

Recovering information from a file requires finding a way to amplify
the information and minimize the camouflaging data. One solution
is to rely on the relatively random quality of image or sound informa-
tion and design a recovery function that strips away relatively ran-
dom information. Whatever is left could hold the information in
question.
Joachim J. Eggers, Jonathan K. Su, and Bernd Girod suggest us-
ing a mechanism where matrix multiplication dampens the cover-
ing data but leaves distinctive watermarks untouched. [ESG00b,
ESG00a] They base their solution on eigenvectors, the particular vec-
tors that are left pointing in the same direction even aftermatrixmul-
tiplication. That is, if M is a matrix and w is an eigenvector, then

Mw is a scalar value known as an eigenvalue. Ev-

ery eigenvector has a corresponding eigenvalue. Most vectors will be
transformed by matrix multiplication, but not the eigenvectors. For
the sake of simplicity, we assume that the eigenvectors are one unit
long— that is,

= λw ,where λ

h

w w =1 .