Towards Optimal Design of Data Hiding Algorithms Against Nonparametric Adversary Models

This paper presents a novel zero-sum watermarking game between a detection algorithm and a data hiding adversary. Contrary to previous research, the detection algorithm and the adversary we consider are both nonparametric in a continuous signal space, and thus they have no externally imposed limitations on their allowed strategies except for some distortion constraints. We show that in this framework no deterministic detection algorithm is optimal. We then find optimal randomized detection algorithms for different distortion levels and introduce a new performance tradeoff between completeness and accuracy when a detection algorithm does not have enough evidence to make an accurate decision.