A Capacity Result for Batch Steganography

Abstract

The problems of batch steganography and pooled steganalysis, proposed in , generalize the problems of hiding and detecting hidden data to multiple covers. It was conjectured that, given covers of uniform capacity and a quantitative steganalysis method satisfying certain assumptions, "secure" steganographic capacity is proportional only to the square root of the number of covers. We now prove that, with respect to a natural definition of secure capacity, and in a suitably asymptotic sense, this conjecture is true. This is in sharp contrast to capacity results for noisy channels.