Cryptography Reference
In-Depth Information
the average user (or the user's computer) to check information for
watermarks.
All of the algorithms are new and relatively untested, but they
still offer exciting possibilities for watermarking files. If they can be
developed to be strong enough to resist attack, people will be able to
use them to track royalties and guarantee the authenticity of the files.
12.4.1 Leveraging Public-Key Cryptography
The standard encryption algorithms can be mixed with stegano-
graphy to offer many of the features of public-key cryptography.
Imagine that you want to embed a message into a file so that only
the person with the right secret key can read it. [And96c]
Here's a straight-forward example:
1. Choose a secret key,
x
.
2. Encrypt the plaintext data with this key using the public key of
the recipient:
E
pk
(
x
)
.
3. Hide this value in a predetermined spot.
4. Use
as a standard key to determine where the other informa-
tion is hidden.
x
If the public-key algorithmand the infrastructure are trustworthy,
only the correct recipient should be able to decrypt
E
pk
(
x
)
and find
x
.
12.4.2 Constraining Hard Problems
One strategy is to use problems that are hard to solve but easy to
verify as the basis for public-key signature. The knowledge of how to
solve the difficult problem acts like a private key and the knowledge
of how to verify it acts like the public key. The real challenge is finding
problems that behave in the right way.
The class of NP-complete problems includes classic computer
science challenges like boolean satisfiability, graph coloring, the
travelling salesman problem, and many others. [GJ79] They are of-
ten hard to solve but always easy to verify. Unfortunately, it is not
always easy to identify a particular problemwith the right mixture of
strength.
This approach has not been historically successful. An early
public-key systemcreated by RalphMerkle andMartinHellman used
an NP-complete problem known as the knapsack.
(Given
n
items
