Security of public watermarking schemes for binary sequences

Abstract

In this paper, we focus on the security aspect of public watermarking schemes. Specifically, given a watermarked sequence Ĩ, we consider smart attackers whose task is to find a non-watermarked sequence I′ using as few calls to the publicly available detection routine as possible. We restrict the media to binary sequences and use Hamming distance as the measure. We study a class of watermarking schemes and give an attacker who uses expected O(d(1 + log(n/k))) calls to find such I′, where d and k are determined by the false alarm and distortion of the scheme, and n is the length of the sequence. This attacker is optimal when k = o(n). By taking the number of calls required as a measure of the security, we can trade-off the requirements on security, false alarm and distortion. © Springer-Verlag Berlin Heidelberg 2003.