Information hiding by coverings

We propose a formal model for embedding information in black and white images and prove the equivalence between the existence of embedding schemes and covering codes. An asymptotically tight bound on the performance of embedding schemes is given. We construct efficient embedding schemes via known coverings. In particular, one of those schemes allows the embedding of up to └log₂(n+1)┘ bits in coverwords of n bits, changing at most one bit, which is twice as good as the scheme of Y.-Y. Chen et al. (see Proc. IEEE Symp. on Computers and Communication - ISCC 2000, p.750-5, 2000). We rewrite some previous schemes with a look towards their covering structures. Finally, we address the problem of active warden in a similar way, giving a model, establishing the relationship with centered codes and concluding by a construction of schemes resistant to active warden.