Analysis of watermarking techniques for graph coloring problem

Gang Qu, Miodrag Potkonjak

1998 · 120 citations · 8 references

DOIFull text

Open access

Concepts

Abstract

We lay out a theoretical framework to evaluate watermarking techniques for intellectual property protection (IPP). Based on this framework, we analyze two watermarking techniques for the graph coloring (GC) problem . Since credibility and overhead are the most important criteria for any efficient watermarking technique, we derive formulae that illustrate the trade-off between credibility and overhead. Asymptotically we prove that arbitrarily high credibility can be achieved with at most 1-color-overhead for both proposed watermarking techniques. 1 Introduction Protecting software from piracy is one of the most crucial issues in computer science. The time-to-market pressure drives intellectual property (IP) into the center of several trends sweeping through today 's electronic design automation (EDA) and application specific integrated circuits (ASIC) industries. The requirement for the exchange of IP in the design of system-on-chip is well documented. As the price of hardware drops a...

References

8