Towards a provably resilient scheme for graph-based watermarking

DOI10.1007/978-3-642-45043-3_6MaRDI QIDQ2864290zbMATH OpenOpenAlexFDO

Authors Lucila Maria Souza Bento, Davidson R. Boccardo, V. G. Pereira de Sá, R. C. S. Machado, Jayme L. Szwarcfiter

Publication date 6 December 2013

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.7262

zbMATH Keywords

algorithmssoftware securitygraph-based watermarkingreducible permutation graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Authentication, digital signatures and secret sharing (94A62)

Abstract: Digital watermarks have been considered a promising way to fight software piracy. Graph-based watermarking schemes encode authorship/ownership data as control-flow graph of dummy code. In 2012, Chroni and Nikolopoulos developed an ingenious such scheme which was claimed to withstand attacks in the form of a single edge removal. We extend the work of those authors in various aspects. First, we give a formal characterization of the class of graphs generated by their encoding function. Then, we formulate a linear-time algorithm which recovers from ill-intentioned removals of $kleq2$ edges, therefore proving their claim. Furthermore, we provide a simpler decoding function and an algorithm to restore watermarks with an arbitrary number of missing edges whenever at all possible. By disclosing and improving upon the resilience of Chroni and Nikolopoulos's watermark, our results reinforce the interest in regarding it as a possible solution to numerous applications.

Recommendations

• Full characterization of a class of graphs tailored for software watermarking
• On the resilience of canonical reducible permutation graphs
• Encoding watermark numbers as reducible permutation graphs using self-inverting permutations
• Error-correcting graphs for software watermarking.
• scientific article; zbMATH DE number 1893217

Cited in

(10)

• scientific article; zbMATH DE number 1952757 (Why is no real title available?)
• TOPOLOGY-PRESERVING WATERMARKING OF VECTOR GRAPHICS
• Models and algorithms for graph watermarking
• On the resilience of canonical reducible permutation graphs
• Encoding watermark numbers as reducible permutation graphs using self-inverting permutations
• Error-correcting graphs for software watermarking.
• Information Security and Cryptology - ICISC 2003
• Dijkstra graphs
• scientific article; zbMATH DE number 1893217 (Why is no real title available?)
• Full characterization of a class of graphs tailored for software watermarking

This page was built for publication: Towards a provably resilient scheme for graph-based watermarking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864290)