Hiding Information Using the Graph Colouring Technique

For a computing system to be trusted, it is equally important to verify that the system performs no more and no less functionalities than desired. Traditional testing and verification methods have been developed to validate whether the system meets all the requirements. They cannot detect the existence or show the nonexistence of unknown undesired functionalities. Security of software as well as information is a significant issue in the Internet age. In order to prevent software from piracy, unauthorised modification and to maintain secrecy of the information embedded into software, many techniques have been developed. Watermarking is a technique that can be used to protect software by embedding some secret information into the software to identify its copyright owner. In this paper, we propose a constrained-based watermarking technique and lay out a theoretical framework to evaluate watermarking techniques for intellectual property protection (IPP). On the basis of this framework, we analyse a watermarking technique for the graph colouring (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 for almost all random graphs, an arbitrarily high credibility can be achieved with at most one-colour overhead for proposed watermarking techniques.