Abstract
One way to protect a digital product is to embed an author’s signature into the object in the form of minute errors. However, this technique cannot be directly applied to protect intellectual properties such as solutions to hard problems which must maintain the correct functionality. This paper proposes a constraint-based watermarking technique and lays out a theoretical framework to evaluate this type of technique. Based on this framework, we analyze three watermarking techniques for the graph coloring problem because of its theoretical importance in complexity theory and numerous applications in real life. The first adds extra edges between some pairs of vertices and therefore forces them to be colored by different colors. The second pre-colors a set of well-selected vertices according to the watermark. And the last introduces new vertices and edges to the graph. Since credibility and overhead are the most important criteria for any efficient watermarking technique, we derive formulae which explicitly illustrate the trade-off between high credibility and low overhead. Asymptotically we prove that for almost all random graphs G n,p , an arbitrarily high credibility can be achieved by all proposed watermarking techniques with at most 1-color-overhead. Numerical simulation on random graphs shows that a large amount of information can be embedded with very low overhead. We also watermark several sets of graphs generated from real-life benchmarks. Almost all the watermarked graphs, with a huge watermark embedded, can be colored with the known minimal number of colors for the original instances with no run-time overhead.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berghel, H., O’Gorman, L.: Protecting ownership rights through digital watermarking. IEEE computer 29(7), 101–103 (1996)
Bollobás, B.: Random Graphs. Academic Press, London (1985)
Boney, L., Tewfik, A.H., Hamdy, K.N.: Digital watermark for audio signals. In: International Conference on Multimedia Computing and Systems, pp. 473–480 (1996)
Cox, I.J., Kilian, J., Leighton, T., Shamoon, T.: A secure, imperceptible yet perceptually salient, spread spectrum watermark for multimedia. Southcon, 192–197 (1996)
Hartung, F., Girod, B.: Digital watermarking of rue and compressed video. In: Proceedings of the SPIE-The Internation Society for Optical Engineering, vol. 2952, pp. 205–213 (1996)
Kahng, A.B., Lach, J., Magione-Smith, W.H., Mantik, S., Markov, I.L., Potkonjak, M., Tucker, P., Wang, H., Wolfe, G.: Watermarking Techniques for Intellectual Property Protection. In: 35th Design Automation Conference Proceedings, vol. 350, pp. 776–781 (1998)
Kirovski, D., Potkonjak, M.: Efficient Coloring of a Large Spectrum of Graphs. In: 35th Design Automation Conference Proceedings, pp. 427–432 (1998)
Nelson, R., Wilson, R.J., (eds.).: Graph Colourings., Harlow,Essex, UK. Longman Scientific & Technical (1990)
Podilchuk, C., Zeng, W.: Perceptual watermarking of still images. In: IEEE Workshop on Multimedia Signal Processing, pp. 363–368 (1997)
Swanson, M.D., Zhu, B., Chau, B., Tewiik, A.H.: Object-based transparent video watermarking. In: IEEE Workshop in Multimedia Signal Processing, pp. 369–374 (1997)
Yeung, M.M., Mintzer, F.C., Braudaway, G.W., Rao, A.R.: Digital watermarking for high-quality imaging. In: IEEE Workshop on Multimedia Signal Processing, pp. 357–362 (1997), http://dimacs.rutgers.edu/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Qu, G., Potkonjak, M. (2000). Hiding Signatures in Graph Coloring Solutions. In: Pfitzmann, A. (eds) Information Hiding. IH 1999. Lecture Notes in Computer Science, vol 1768. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10719724_24
Download citation
DOI: https://doi.org/10.1007/10719724_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67182-4
Online ISBN: 978-3-540-46514-0
eBook Packages: Springer Book Archive