encoding watermark integers as self-inverting permutations
In a software watermarking environment, several graph theoretic watermark methods use integers as watermark values, where some of these methods encode the watermark integers as reducible permutation graphs (RPG; these are reducible control-flow graphs with a maximum out-degree of two). Since there is a one-to-one correspondence between self-inverting permutations and isomorphic classes of RPGs, for encoding watermark integers most of the watermarking methods use only those permutations that are self-inverting. In this paper we present an efficient algorithm for encoding integers as self-inverting permutations. More precisely, our algorithm takes as input an integer w, computes its binary representation b 1 b 2 ...b n , and then produces a self-inverting permutation ?* in O(n) time. Moreover, we also present an algorithm for decoding a self-inverting permutation; our algorithm takes as input a self-inverting permutation ?* produced by the encoding algorithm and returns its corresponding integer w in O(n) time, where n is the length of the input permutation.
encoding watermark self-inverting permutations permutations graphs algorithms decoding