Towards a Provably Resilient Scheme for Graph-Based Watermarking

Abstract

Techniques of watermarking/fingerprinting concern the embedding of identification data into a digital object, allowing for later claims of authorship/ownership and therefore discouraging piracy. Graph-based watermarking schemes comprise an encoding algorithm, which translates a given number (the identifier, usually a positive integer) onto some appropriately tailored graph (the watermark), and a decoding algorithm, which extracts the original identifier from a given watermark. Collberg, Kobourov, Carter and Thomborson (Error-correcting graphs for software watermarking, WG’03) introduced one such scheme, meant for software watermarking, in which an integer key was encoded onto a reducible permutation graph. A number of interesting ideas have further improved the original scheme, including the formulation of a particularly promising linear-time codec by Chroni and Nikolopoulos. We extend the work of these authors in various aspects. First, we characterize the class of graphs constituting the image of Chroni and Nikolopoulos’s encoding function. Furthermore, we formulate a novel, linear-time decoding algorithm which detects and recovers from ill-intentioned removals of k ≤ 2 edges. Finally, our results also include the detection of k ≤ 5 edge modifications (insertions/deletions) in polynomial time and a proof that such bound is tight, so the resilience of the considered watermarking scheme is fully determined. Our proof that graphs of a well-characterized class can detect and recover from bounded-magnitude distortive attacks reinforces the interest in regarding those graphs as possible watermarking solutions to numerous applications.

Work partially supported by Eletrobrás — Distribuição Rondônia, DR/069/2012.