Chapter 12. Keys

12.1. The Key Vision

A new directive from the National Science Foundation ordered all researchers to stop looking for “keys” that will dramatically unlock the secrets behind their research. The order came swiftly after a new study showed that a “wholistic vision” was a more powerful metaphor than the lock and key. Administrators at the National Science Foundation predicted the new directive would increase discoveries by 47% and produce significant economies of effort.

The recent news of the metaphoric failure of the lock and key image shocked many researchers. Landon P. Murphy, a cancer specialist at Harvard's Women and Children's Hospital, said, “We spent our time searching for one key insight that would open up the field and provide us all of nature's abundant secrets. One key insight can do that for you.”

In the future, all researchers will train their minds to search for a “wholistic picture” that encompasses all of their knowledge. An inclusive understanding is thought to yield more discoveries in a faster time period because the grand vision can often see the entire forest not just the trees.

“Let's say you're on top of a mountain. You can see much further than you can at the base– even if you have a key to the tunnel under the mountain.” said Bruce Konstantine, the Executive Deputy Administrative Aide at the NSF. “We want our researchers to focus on establishing the grand vision.”

Some scientists balked at the new directive and countered with a metaphor of their own. “Sure you can see for miles but you can't see detail.” said Martin Grubnik, a virologist at the University of Pittsburgh. “Some of us need to focus on the small things and the details to make progress. That's the key.”

Konstantine dismissed this objection and suggested that the virologists might make more progress if they avoided a narrow focus.

“The key insight, or perhaps I should say the true vision, is that scientists who focus too narrowly avoid seeing the big picture. We want more big pictures. If that means abandoning the hope for one key, so be it.”

12.2. Extending Control

Most of the game of steganography involves finding a set of algorithms that can make one chunk of data look like another. In some instances, camouflaging the existence of the data is not enough. Stronger attacks require stronger measures and one of the most versatile is adding some key bits to the algorithm.

The key is some relatively small collection of bits that plays a strong role in the algorithm. If someone doesn't hold the right key, they can't unlock certain features of the algorithm. The bits of information in the key are somehow essential for manipulating the data.

Most of the keying techniques used in steganography are extensions of the solutions used in basic cryptography. Some of the basic types include:

• Secret Keys One key is used to hide the information and the same key must be available to uncover the information. This is often called symmetric or private key steganography. The second term isn't used in this book to avoid confusion with public-key approaches.
• Public Mechanisms or Public Keys One key hides the information and a different key uncovers it. Some call these asymmetric because the algorithms separate the functions. These solutions are often useful for watermarking information because someone can uncover the information without the power to hide new information— that is, the power to make new copies with the person's watermark. None of the algorithms described here offer a solution with any of the simplicity of the best public-key encryption systems. They often rely on difficult problems or some obscurity to provide some form of a “private key”. In many cases, there is no private key at all. The public key is just used to verify the signature. Some of the other solutions provide public-key behavior by encrypting and decrypting the hidden information with standard public-key algorithms.
• Zero-Knowledge Proofs These systems allow the information hider to secure information so that it's existence can be revealed without revealing the information itself. The technique can also be useful for watermarking because the information hider can prove they hid the information without giving someone else the power to hide the same information. That is, to make copies with the same watermark.
• Collision Control Codes Let's say you have several copies of a document. These codes try to prevent you from combining the copies in ways to obscure the information hidden inside. Some basic attacks on watermarking information, for instance, involve averaging several different copies. These solutions resist these attacks.

There are a number of approaches for implementing algorithms that fall into these classes. The simplest is to use basic secret-key or public-key algorithms on the data before it is handled by the steganography algorithm. The encryption algorithm and the hiding algorithm are kept separate and distinct from each other.

Separating the functions is easier to understand and it has one practical advantage: encryption algorithms naturally make data look more random and random data is often the best kind for steganography. Encrypting the data often makes sense even if the secrecy is not necessary because encryption is one of the simplest ways to increase the randomness of the data. Of course, this approach can occasionally produce data that is too random, a problem discussed in depth in Chapter 17.

Keeping the encryption separate from the hiding is more intellectually straight-forward. Good encryption algorithms can be mixed or matched with good steganographic solutions as the conditions dictate. There's no need to make compromises.

But splitting the two processes is also limiting because the hiding algorithm is the same for everyone. Anyone can recover the hidden bits because the algorithm is essentially public. Anyone who uses it to recover bits on one occasion can now use it again and again in other situations. They may not be able to do anything with the bits because the encryption is very strong, but they will be able to find them relatively easily and replace them with bits of their own.

Keying the hiding process ensures that only people with the right key can either hide or recover bits. This restricts attackers by adding an additional layer of complexity to the process.

Many of the basic algorithms in this book use generic keys to control the random choices made by them. If an arbitrary decision needs to be made, then a cryptographically secure random number generator driven by a key is one of the simplest mechanisms for adding a key to the scheme.

The algorithms in Chapter 9 hide information in the least significant bits of image and sound files by selecting a subset of elements. This selection process is driven by a random number generator that repeatedly hashes a key. In Chapter 13, the functions used to compute the sorted list of data elements can include a key. If the same stream of random numbers isn't available, the bits can't be extracted.

More sophisticated systems integrate the key even deeper into the algorithm. Some try to constrain how the answer to some hard problem is constructed. Others try to limit how it is encoded in the data.

Many of these newer advanced systems show how just about any computational processes can be tweaked or distorted to include a few extra bits. Most algorithms include some arbitrary decisions about location, order, or process and which can be driven by some key. In the best cases, the authors understand the problem well enough to provide some actual arguments for believing that the process is hard to decrypt without the key.

12.3. Signing Algorithms

Many of the keying algorithms provide some kind of assurance about the documents authenticity by acting like digital signatures for the document. These solutions are quite useful in all situations where digital signatures on arbitrary files provide some certainty. They're also especially useful for watermarking. The ideal algorithm allows the file's creator to embed a watermark in such a way that only the proper key holders can produce that watermark.

The basic solution involves separating the image or audio file into two parts. The first holds the details that will remain unchanged during the steganography. If the information is hidden in the least significant bits, then this part is the other bits, the most significant ones. The second part is the bits that can be changed to hide information. This set may be defined and hence controlled by a key.

A digital signature on the file can be constructed by hashing the unchangeable part, signing the hash value with a traditional digital signature function, and then encoding this information in the second part reserved for hidden information. The digital signature may be computed with traditional public-key algorithms like RSA, or it may use more basic solutions with secret key algorithms or even hash functions.[Won98, Wal95a]

This process uses two keys that may or may not be drawn from the same set of bits. The first is used to define the parts of the file that may be changed. It could be a random number stream that picks pixels to hide information. The second key actually constructs the signature.

This approach is direct, and easy to code, but it hides the information in the most succeptable part of the file. Compression algorithms and other watermarks can damage the information by changing the data in this section. [CM97]

Jessica J. Fridrich and Miroslav Goljan suggest self-embedding a copy of an image in itself. Details from one block are embedded in another block across the image. Cropping or other tampering can be reversed. [FG99]

The mechanism can also be extended by splitting the file into numerous sections. The signature for section i can be embedded into section i+1. Figure 12.1 shows how this might be done with a file broken into five sections. The data from one section is hidden in the next section. Separating the hiding also can provide an indication of where any tampering took place.

Figure 12.1. An embedded digital signature can be woven into a file. In this visual allegory, the file is broken up into five chunks. Each chunk is broken up into two part– one that remains unchanged and the other that hides information. The data from section i is used to create a digital signature that is embedded in section i + 1.

12.4. Public-Key Algorithms

Many researchers are trying to develop “public-key” algorithms for hiding information that provide many of the same features as public-key cryptography. The systems allow a user to hide information in such a way that anyone can recover it, but ideally in a way that no one can create new data in the right format.

This feature is desirable for watermarks because it is ideal for 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 x as a standard key to determine where the other information is hidden.

If the public-key algorithm and 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 often hard to solve but always easy to verify. Unfortunately, it is not always easy to identify a particular problem with the right mixture of strength.

This approach has not been historically successful. An early public-key system created by Ralph Merkle and Martin Hellman used an NP-complete problem known as the knapsack. (Given n items with weights {w¹, ldots, wⁿ}, find a subset that weighs W pounds.) Their algorithm created custom knapsacks that appeared to offer a guarantee that they were hard to pack exactly. Only someone with a secret value, the private key, could determine the right subset of objects to put in the knapsack with ease. After some equally hard work, a human, Adi Shamir found a general algorithm that will break the system without threatening the general NP-complete problems. It exploited the key generation process that tried but failed to find enough complicated sizes for the knapsacks. [Sha82, Lag84, Odl84]

No one else has had luck with NP complete problems. They seem theoretically secure because there's no general algorithms for solving them quickly, there are a number of fast heuristics that find solutions in almost all cases. Indeed, no one has a good mechanism for identifying a small subset of problems that are difficult enough to offer some guarantees.

In one solution, Gang Qu imagines that the ability to create these solutions is what is being protected by a watermark. A person who knows how to solve the travelling salesman problem optimally may market their solutions to airlines, businesses or traveling salesforces. To protect against piracy of their custom itineraries, they could hide some signature information in the file that proves the solutions are theirs. A competing business may develop their own solutions, but anyone can check the provenance by looking for this hidden information.

The technique hides information in the solutions to the difficult problems by forcing certain parameters to take certain values. [Qu01, KQP01] Anyone can examine the solution and check the parameters, but it should be difficult to assemble a new solution because the problem is presumably hard. The approach does not really require a set of bits labeled a “public key”, but it still behaves in much the same way.

Information is hidden in the solution to the problem by introducing new constraints on the solution. The classic boolean satisfiability problem, for instance, takes n boolean variables, {x¹, …, xⁿ} and tries to assign true or false values to them so that a set of boolean clauses are all true. Information can be encoded in the answer by forcing some of the variables to take particular values— say x¹⁴ = T,x²⁵ = F,x³⁹ = F,x⁵⁹ = T and x⁷⁷ = T might encode the bitstring 10011. Of course, adding this extra requirement may make a solution impossible, but that is a chance the designers take.

The technique can be applied to many NP-complete problems and other problems as well. Many problems have multiple solutions and information can be hidden by choosing the appropriate solution that also encodes the information. Figure 12.2 shows a graph colored so that several nodes take fixed colors. One way to encode the information is to grab pairs of nodes and force them to have either the same or different colors. Two nodes can be forced to have the same color by merging them while the algorithm looks for a solution. Two nodes can be kept different by adding an edge that connects them. Other problems usually have some latitude.

Figure 12.2. A graph colored so that no two adjacent nodes have the same color. Information can be encoded in this solution by forcing certain nodes to certain colors.

The process can be strengthened by hashing steps along the way. Let K⁰ be a creator's original watermarking information. It might be their name, it might be an email address, or it could be a reference to some big table of known creators. Let H be a strong hash function like MD5 or SHA. Let {C¹, …, Cⁿ} be a set of constraints to the problem that are open for twiddling to hold information. These may be extra variables in a boolean satisfiability problem that can be set to true or false. Or they could be nodes in a graph that might hold different values. For the sake of simplicity, assume that each constraint can encode one bit. The following loop will encode the watermark:

1. Let Kⁱ = H(K^i-1, C^i-1). The hashing function should be fed both the information encoded in C^i-1 and some data about the structure of C^i-1 itself. This data might include the node numbers, the variable names, or the boolean formulae. (Set C⁰ to be a null string.)
2. Extract one bit from Kⁱ and encode it in Cⁱ.

Repeat this for all n constraints.

The watermark can be tested by repeating the process. Any skeptical inquirer can get K⁰ from the creator and step through the process, 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 designers, 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, “Copyright 2001 Bob Chiphead”.

The technique can be applied to more general information-hiding problems or watermarking problems, but it has limitations. The creator must have the ability to find solutions to difficult problems– solutions that are difficult for the average person to aquire. The simplest 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 similar solution to mint small tokens, Peppercoin. [Riv04]

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 information and design a recovery function that strips away relatively random information. Whatever is left could hold the information in question.

Joachim J. Eggers, Jonathan K. Su, and Bernd Girod suggest using a mechanism where matrix multiplication dampens the covering data but leaves distinctive watermarks untouched. [ESG00b, ESG00a] They base their solution on eigenvectors, the particular vectors that are left pointing in the same direction even after matrix multiplication. That is, if M is a matrix and w is an eigenvector, then Mw = λw, where λ is a scalar value known as an eigenvalue. Every 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^hw = 1.

Exploiting this property of matrix multiplication requires assuming that the data in the file is relatively random and comes with a mean value of zero. Sound files fit this model, but image files usually fail because they consist of bytes that range between 0 and 255. Any file can be converted into one with a zero mean value by calculating the mean and subtracting it from each entry. The result may not be sufficiently random for this algorithm, but we will assume that it is.

Let x be a vector of data where the watermark will be hidden. We assume that it comes with a zero mean and is sufficiently random. What is sufficiently random? Perhaps it's better to define this by describing the effect we want. Ideally, we want x^hMx = 0 or at least sufficiently close to zero. Then it will drop out of the computation and only the watermark will be left.

Let w be an eigenvector of some matrix, M, and λ be the corresponding eigenvalue. Mw = λw. This vector can be used as a watermark and added to the camouflaging data, x, with a weight, β. Ideally, β is chosen so that x + βw is perceptually identical to x and the watermark can be extracted.

The watermark is extracted from the data by computing

If the assumption about the randomness of x holds, the first three terms will be close to zero leaving us with β² λ(w^hw) = β²λ.

A public-key system can be established if the values of M, β, and λ are distributed. Anyone can test a file, y, for the presence or absence of the watermark by computing y^hMy and determining whether it matches β² λ.

This approach still has a number of different limitations. First, the number of elements in x and w must be relatively large. Eggers, Su and Girod report results with lengths of about 10,000 and about 100,000. Larger values help guarantee the randomness that pushes x^hMx to zero.

Second, finding the eigenvectors of M is just as easy for the message creator as any attacker. One solution is to choose an M which has many different eigenvectors, {w¹, …, wⁿ} that all come with the same eigenvalue λ. The attacker may be able to identify all of these eigenvectors, but removing the watermark by subtracting out the different values of wⁱ, one after another, could be seen as a brute-force attack.

Of course, the ease of finding the eigenvectors means that someone can insert a fake watermark by choosing any eigenvector, wⁱ, that comes with an eigenvalue of λ. This means that the algorithm can't be used to generate digital signatures like many of the classic public key algorithms, but it might still be of use for creating watermarks that prevent copying. A pirate would find little use in adding a signal that indicated that copying should be forbidden.

More sophisticated attacks may be possible. The authors credit Teddy Furon for identifying a trial-and-error approach to removing watermarks with this tool by changing the scale for the part of the signal in the space defined by the eigenvectors, {w¹, …, wⁿ}, with length λ.

The algorithm can be tuned by choosing different values of M. The authors particularly like permutation matrices because an n x n matrix can be stored with n − 1 values. “Multiplication” by a permutation matrix is also relatively easy. Using the matrix designed to compute the discrete cosine transform is also a good choice because the computation is done frequently in image and sound manipulation.

This solution is far from perfect and its security is not great. Still, it is a good example of how a function might be designed to minimize the camouflaging data while amplifying the hidden data. The process is also keyed so that the value of M must be present to extract the hidden message.

12.4.4. Removing Parts

Many of the algorithms in this book hide information by making a number of changes to a number of different locations in the file and then averaging these changes to find the signal. The proceding section (12.4.3), for instance, may add hundreds of thousands of small values from the watermark eigenvector into the file. The spread-spectrum-like techniques from Chapter 14 will spread the signal over many different pixels or units from a sound file. The signal is extracted by computing a weighted average over all of them.

One insight due to Frank Hartung and Bernd Girod is that the information extractor does not need to average all of the locations to extract a signal. [HG97] The algorithms already include a certain amount of redundancy to defend against either malicious or accidental modifications to the file. If the algorithms are designed to carry accurate data even in the face of changes to an arbitrary number of elements, why not arrange for the receiver to skip that arbitrary number of elements all together?

Consider this algorithm:

1. Create n “keys”, {k¹, …, kⁿ}.
2. Use cryptographically secure random number generators to use these keys to identify n different sets of m elements from the file.
3. Tune the hiding algorithm so it can hide information in mn elements in such a way that the information can be recovered even if (n − 1)m elements are not available or damaged.
4. Hide the information.
5. Distribute the n “keys” to the n different people who might have a reason to extract the information. The algorithm will still work because the information was hidden with such redundancy that only one subset is necessary.

Hartung and Girod use the term “public-key” for the n values of {k¹, …, kⁿ}, even though they do not behave like many traditional public keys. The keys do offer a good amount of antifraud protection. Anyone possessing one ki can extract the information, but they cannot embed new information. If the holder of the value of ki tries to embed a new signal, it will probably be invisible to the holders of the other n − 1 keys because their keys define different subsets. The holder of ki can change the elements as much as possible, but this won't change the information extracted by others.

Of course, this approach does have limitations. The values of kⁱ are not truly public because they can't circulate without restrictions. They also can't be used to encrypt information so that they can only be read by the holder of a corresponding private key. But the results still have some applications in situations where the power of keys needs to be reined in.

12.5. Zero Knowledge Approaches

Zero knowledge proofs are techniques for proving you know some information without revealing the information itself. The notions began evolving in the 1980s as cryptographers and theoretical computer scientists began exploring the way that information could be segregated and revealed at optimal times. In one sense, a zero knowledge proof is an extreme version of a digital signature.

Here's an example of a zero knowledge proof. Let G be a graph with a set of nodes ({v¹, v², …, vⁿ}) and a set of edges connecting the nodes ({(vⁱ, v^j), …}). This graph can be k-colored if there exists some way to assign one of k different colors to the n nodes so that no edge joins two nodes with the same color. That is, there does not exist an i and a j such that f(vⁱ) = f(v^j) and (vⁱ, v^j) is in the set of edges. f is the coloring function. Figure 12.3 shows one graph that is 4-colored.

Figure 12.3. A graph where the nodes are assigned one of four colors.

Finding a k-coloring of an arbitrary graph can be a complicated and difficult process in some cases. The problem is known to be NP-complete, [GJ79] which means that some instances seem to grow exponentially more difficult as more nodes and edges are added. In practice, a coloring for many graphs can be found relatively quickly. It's often harder to find difficult graphs and this is one of the practical limitations of using zero knowledge proofs in applications. There are a number of details that make it difficult to produce a working and secure implementation of this idea.

Let's say you know a coloring of some graph and you want to prove that you know it without actually revealing it to another person, the skeptical inquirer. Here's an easy way to prove it:

1. Create a random permutation of the coloring, f′. That is, swap the various colors in a random way so that f′(vⁱ) ≠ f′(v^j) for all (vⁱ, v^j) in the graph.
2. The skeptical inquirer can give you a random bit string, S. Or S might be established from an unimpeachable source by hashing an uncorruptible document. If the zero knowledge proof is going to be embedded in a document, this hash might be of the parts of the document that will not be changed by the embedding.
3. Create n random keys, p¹ …pⁿ and use an encryption function to scramble the string S + i + f′(vⁱ) for each node in the graph where + stands for concatenation. Ship the encrypted versions to the skeptical inquirer.
4. The skeptical inquirer chooses an edge at random from the graph, (v^a, v^b) and presents it to you.
5. You ship p^a and p^b to the skeptical inquirer, who uses them to decrypt the encrypted version of the colors, f′(v^a) and f′(v^b). If the two are different, the skeptical inquirer knows that you've proven that you know how to color at least one part of the graph. Figure 12.4 shows two adjacent nodes being revealed.

   Figure 12.4. In a zero-knowledge proof, the colors of the nodes are encrypted and sent to the skeptical inquirer who asks to have two adjacent nodes revealed.

   

This process should be repeated until the skeptical inquirer is satisfied. If the edges are truly chosen at random, any mistakes in the coloring stand an equal chance of being revealed at each step. The randomness prevents the prover from anticipating the choice and selecting f′. Eventually, any weakness or miscoloring will show through.

Zero knowledge proofs like this may be useful in the world of hidden information because they allow the information hider to control how and when the information is revealed to another person. The structure of the proof, however, guarantees that no information is revealed. The proof can't be repeated by someone else or used as a basis to remove the information. This solution may be useful for watermarking applications where a copyright holder may want to prove that they are the rightful owner without revealing the technique to others.

In theory, any zero-knowledge proof can be used as a watermark. Every proof begins with a set of bits that identify the instance of the problem. Imagine that m iterations of the encrypted graph procedure described above are sufficient to prove knowledge of the graph coloring. The proof can be embedded in a document with these steps:

1. Create a value of S by hashing the parts of the document that won't be modified during the embedding process. These might be the most significant bits or some other high-pass filtering of the document.
2. Create m permutations of the coloring: f′¹, f′², … f′^m.
3. Create m x n keys, p^i,j, where i stands for the iteration of the proving algorithm, (1 ≤ i ≤ m), and j stands for the node, (1 ≤ j ≤ n).
4. Scramble the coloring of the n nodes for each iteration of the proof by encrypting the string S + i + j + f′ⁱ(v^j), where + stands for concatenation.
5. Embed each of the encrypted colors and the description of the graph in the document. If necessary, the encrypted colors can be embedded in hidden locations described by p^i,j. For instance, this value could be used as a seed for a cryptographically secure random number generator that chooses a string of pixels to hide the signal.

If someone challenges the document, they can ask the information hider to prove that they know how to color the graph hidden away inside of it. Presumably, this problem is difficult to solve and only the person who hid the graph would know how to color it. The skeptic could repeat these steps m times. Let i stand for the iteration.

1. The skeptic recovers the graph.
2. The skeptic assembles S by examining the unchanged parts of the document.
3. The skeptic chooses a random edge, (v^a, v^b).
4. The prover reveals p^i,a and p^i,b. These values can be used to locate the encrypted colors and then decrypt them. If they don't match, the process continues. If they do match, the prover is toast.

This solution offers a number of advantages if a suitable graph can be found. The person hiding the information can prove they hid it without revealing enough information for someone to duplicate the proof. Each skeptic is going to choose the edges at random, and it's unlikely that the all of them will be repeated.

This static version is not as powerful as the interactive version because the prover must lock in the colorings. If a skeptic is able to get the prover to repeat the algorithm a number of times, eventually the skeptic will gather enough of the keys, p^i,j, to stand a good chance of proving they know the graph coloring. Eventually, the prover will reveal the entire colorings. This slow leak of information means that the proofs are not zero-knowledge. This process may still be practical if m and n are large enough and the number of times the proof is executed is kept small enough.

Finding a suitable graph is not an easy process. There are many different kinds of zero-knowledge proofs that can be embedded in similar situations, but most of them are not particularly practical. The proofs rely on problems that can be hard in the worst cases, but are usually rather easy to compute. Finding and identifying guaranteed difficult instances of the problem is not easy. One of the first public-key encryption systems developed by Ralph Merkle and Martin Hellman used one NP-complete problem known as the knapsack. Eventually, all versions of the algorithm were broken and many grew skeptical that basic NP-complete problems could be trusted to produce difficult instances.

12.5.1. Discrete Logs for Proofs

Scott Craver developed one mechanism for zero knowledge watermarking that relies on the difficulty of the discrete log problem. (Given y, find x such that y = g^x mod q, where q is a prime chosen according to some increasingly strict guidelines for ensuring the strength of cryptographic systems based on the difficulty of the discrete log problem.) This solution succeeds because it uses a number of fake watermarks as decoys. Ideally, anyone trying to tamper with the watermark must remove the real one as well as all of the decoys. Ideally, there will be so much information that removing them all will substantially change the image.

Let x be the secret key that acts as a watermark. This algorithm will allow the information hider to prove they know x without revealing x itself. The prover hides y¹ = g^x mod q in the document using a key, p¹, to choose the locations in the document.

The prover then extracts n-1 fake watermarks that happen to be in the document. That is, the prover chooses n − 1 keys, p², …, pⁿ, to extract n − 1 values, y², …, yⁿ. Using fake decoys derived from the document can help increase the strength of the watermark. The more there are, the more likely that removing them will damage the image. In some cases, the prover may actually insert them if this makes the task easier.

When a skeptic shows up with the document, the prover can show knowledge of x without giving the skeptic the power to repeat this process. The decoys prevent the skeptic from ever learning which value of yⁱ has a known log. Here are the steps.

1. The prover presents the keys, p¹, …, pⁿ, to the skeptic.
2. The skeptic recovers the values of yⁱ.
3. This loop is repeated as many times as necessary.
   • The prover generates n blinding factors, b¹, …, bⁿ, that are used to scramble the watermarks by computing wⁱ = g^biyⁱ.
   • The prover scrambles up these values of wⁱ before shipping them to the skeptic.
   • The skeptic flips a coin and makes one of two demands to the prover:
     • Tell me all of the blinding values, b¹, …, bⁿ. Knowing these, the skeptic can check to make sure that there is one legitimate value of w^i. for each value of yⁱ.
     • Prove you know the log to one of these values. The prover accomplishes this by revealing x+b¹ mod(q-1). This is the log of w¹ = g^b1y¹ = g^b1g^x = g^x+b1 mod q.

At each iteration, the prover must reveal one half of the solution. The structure makes it unlikely that a skeptic will turn around and successfully repeat the proof to someone else. It is not possible to take the answers from one and use the information to answer the other. Only someone who knows the value of x can do it.

There are still limitations to this algorithm. The prover must reveal the location of the different blocks of bits, something that leaves them succeptible to destruction. The decoys increase the workload of the attacker and increase the probability that removing all of the information will substantially change the document.

One way to improve the strength of the algorithm is to mix in a number of real marks with the decoys. That is, the prover arranges to hide multiple values of yⁱ where the prover knows the value of xⁱ such that yⁱ = g^xi mod q. The prover can then use a different subset of values with each skeptic as long as the prover knows one value of xⁱ for the values in the subset. Of course, multiple copies and multiple blocks and help reduce this danger but they do not eliminate it. Eventually, all of the marks will be revealed.

12.6. Collusion Control

Another technique for “keying” watermarks is occasionally called “collusion control” for lack of a better term. Imagine that you create two documents, d¹ and d², with watermark bits w¹ and w² encoding the true owner's identity. Watermarking is an imperfect science, so despite your best efforts someone trying to cheat the system compares the files and finds where they are different. The cheater injects random noise into these locations, effectively changing half of the bits. What happens to the watermarks?

Basic systems would fail here. If w¹ = 001010111 and w² = 001010100, then only the last two bits are different. A new watermark, 00101010101 would implicate someone else.

Collusion control systems that can combat this were first introduced by Dan Boneh and James Shaw. [BS95] Their mechanism acts like an extension of error-correcting codes.

Error-correcting codes are described in Chapter3.

Here's a example. Let S be the set of n-bit code words with only a single bit set to 1. If n = 4, then S = {1000,0100, 0010,0001}. Let one code word be assigned to each document. If two document holders collude, they will only find that their watermarks differ by two bits. Boneh and Shaw call this a frameproof code and note that any code that is frameproof for n users must come with n bits. So this construction is optimal.

For example, let Alice's watermark be 0100 and Bob's be 0001. Someone tries to erase the watermark by creating a synthetic one blending the two files. After identifying all bits that are different, the attacker chooses half from Alice's file and half from Bob's. What happens if someone compares a file from Alice and a file from Bob to find differences? If someone creates a new file with the watermark 0101, then both Alice and Bob will be implicated. Anyone examining the file can trace it back to both of them. Changing 50 percent of the bits will produce one of the two watermarks. One will remain implicated.

Of course, a clever attacker may flip both to zero to produce the watermark 0000. This will implicate no one, but it is not easy to generate. Anyone trusting the watermark will not choose bit vectors like this example. They may XOR them with a secret password and the attacker won't know what is up and down, so to speak. A zero in the fourth position may identify Bob after it is XORed with the secret vector.

Boneh and Shaw extend this idea by combining it with ideas from the world of error-correcting codes. Each attacker will need to flip many bits before the watermark is effectively erased, because the error-correcting codes compensate for random flips.

12.7. Summary

Most algorithms in this book can add additional security with a key. This key can be used to create a pseudo-random bit stream by computing successive values of some encryption or hash function:

This bit stream can be used to either choose a subset of the file or to control how it is encoded at each location. Only someone with the same key can recover the information. Of course, it also makes sense to encrypt the file with another key and a cryptographically strong algorithm before it is inserted.

Keying the algorithm defends against the often public nature of computer standards. If the software is going to be used often and distributed to many people, then the algorithms inside of it become public. Adding a key to the algorithm increases its strength dramatically.

The Disguise Many of the algorithms add an extra layer of disguise by using the key to modify the behavior of the algorithm. This means that any attacker will not be able to extract the data with knowledge of the algorithm alone.

• How Secure Is It? Pseudo-random bit streams created by repeated encryption or hashing can be quite secure.
• How to Use It Replace any random number generator used to add noise with a pseudo-random keyed stream, which can also be used to extract particular subsets or to rearrange the data itself. The algorithms in Chapter 13, for instance, use a keyed encryption function to change the data's order.

Further Reading

• Luis von Ahn and Nicholas J. Hopper provide a good theoretical foundation for understanding when steganography can offer public-key-like behavior. [vAH04]
• Michael Backes and Christian Cachin suggest that a good public-key steganography system is built from a good public-key crypto system offering output indistinguishable from a random source. This allows them to produce a system that can resist active attacks. [BC05]