A Software Watermarking Method Based on Public-Key Cryptography and Graph Coloring

A new software watermarking method based on public-key cryptography and graph coloring problem (GC) is proposed in this paper. The method with good stealth and security can be applied to protect and verify software copyright. Firstly, the copyright information of ownership should be encrypted for software by RSA public-key cryptography algorithm to ensure that the information is confidentiality, integrity and certainty and prevent the information from tampering and forging. Secondly, the message encrypted is embedded into software by the watermarking technique for the GC problem which has the advantage of being very stealthy due to the fact that it doesn´t add any code. Experiments show that a high level of stealth and security can be achieved with at most 1-color-overhead for proposed watermarking method.