Grey-Box Steganography

We propose a new model of steganography which combines partial knowledge about the type of covertext channel with machine learning techniques to learn the covertext distribution. Stegotexts are constructed by either modifying covertexts or creating new ones, based on the learned hypothesis. We illustrate our concept with channels that can be described by monomials. A generic construction is given showing that besides the learning complexity, the efficiency of secure grey-box steganography depends on the complexity of membership tests and suitable modification procedures. For the concept class monomials we present an efficient algorithm for changing a covertext into a stegotext.