Computational Aspects of Digital Steganography

1 Introduction

Digital Steganography aims at hiding secret data in unsuspicious cover media. The field has been actively investigated since the early 1990s. In most cases, the cover media chosen are multimedia data, such as images, audio or video. For this reason, many impulses in steganography research come from statistics, signal and image processing with a focus on heuristic algorithms for hiding and experimental methods for detecting hidden information. In the early years of scientific investigations this focus caused a lack of theoretical analyses on fundamental properties of steganographic systems, namely capacity, security and tractability.

Starting in the late 1990s, theoretical analyses of steganography began to be conducted, concerned primarily with security and capacity aspects, which unfortunately have mostly been neglected by practitioners in the field. This is in part due to unrealistic assumptions and simplifications that have been made in order to cope with the difficult problem of formal modelling of steganography. In the case of capacity – besides some superficial practical analyses – a good understanding from an information-theoretic point of view has been achieved (see e.g. the seminal paper by Moulin and O’Sullivan, 2003), but there is still a lack of some guiding theory describing any information-hiding system achieving maximum capacity. Moreover, the focus of the mentioned study was on active adversaries, a scenario that better suits digital watermarking than steganography, where typically passive adversaries are considered. Because of this we view capacity as a topic that will have to receive renewed attention in the future and thus leave it out of our current study. Regarding security, the focus of theoretical investigations so far has been on the maximum achievable security in different attack scenarios, which has led to interesting insights, but not yet to more secure stegosystems, as practical implementations of such systems prove to be difficult, if not unfeasible in terms of computational complexity. So the situation of steganography seems in some respects similar to that of cryptography some fifty years ago, where the existence of secure systems, such as the one-time pad, was known, but these could not be practically implemented.

When looking at stegosystems that have been practically implemented, however, one finds that the time-span from announcement as the latest and greatest system to the first successful detection by steganalysis often lasts only some two or three years. Because this situation does not appear to change in spite of all efforts by the steganography community, the question arises whether bringing reliable security into real-life systems can be achieved at all. Using experience and methods from cryptography and theoretical computer science one can expect to find answers to the important question if the field of steganography can reach levels of security that are available today in cryptography.

This chapter provides an overview of previous work on theoretical analyses of steganography, in which the central question concerns the security of given systems. Several definitions of secure steganography have been proposed in the literature, but most of them make the rather unrealistic assumptions of unlimited computational power for the parties involved and complete knowledge of the cover and stegotext distributions. We focus on formal models of secure systems that make more realistic assumptions of limited computational resources and restricted access to covertext distributions. This allows us to look at steganographic secrecy from a computational complexity point of view and to obtain provable security based on widely accepted complexity assumptions, as e.g. the existence of one-way functions. Such security evidence is commonly accepted in the field of cryptography.