Provably Secure Steganography
project report tiger Active In SP Posts: 1,062 Joined: Feb 2010 
10022010, 10:56 PM
Steganography is the problem of hiding secret messages in innocentlooking public communication so that the presence of the secret messages cannot be detected. This paper introduces a cryptographic formalization of steganographic security in terms of computational indistinguishability from a channel, an indexed family of probability distributions on cover messages. We use cryptographic and complexitytheoretic proof techniques to show that the existence of oneway functions and the ability to sample from the channel are necessary conditions for secure Steganography. We then construct a steganographic protocol, based on rejection sampling from the channel that is provably secure and has nearly optimal bandwidth under these conditions. This is the first known example of a general provably secure steganographic protocol. We also give the first formalization of robust Steganography, where an adversary attempts to remove any hidden messages without unduly disrupting the cover channel. We give a necessary condition on the amount of disruption the adversary is allowed in terms of a worst case measure of mutual information. We give a construction that is provably secure and computationally efficient and has nearly optimal bandwidth, assuming repeatable access to the channel distribution. 


seminar flower Super Moderator Posts: 10,120 Joined: Apr 2012 
31072012, 04:06 PM
Provably Secure Steganography
Provably Secure.pdf (Size: 269.5 KB / Downloads: 23) Abstract Informally, steganography is the process of sending a secret message from Alice to Bob in such a way that an eavesdropper (who listens to all communications) cannot even tell that a secret message is being sent. In this work, we initiate the study of steganography from a complexitytheoretic point of view. We introduce denitions based on computational indistinguishability and we prove that the existence of oneway functions implies the existence of secure steganographic protocols. Introduction The scientic study of steganography began in 1983 when Simmons [17] stated the problem in terms of communication in a prison. In his formulation, two inmates, Alice and Bob, are trying to hatch an escape plan. The only way they can communicate with each other is through a public channel, which is carefully monitored by the warden of the prison, Ward. If Ward detects any encrypted messages or codes, he will throw both Alice and Bob into solitary connement. The problem of steganography is, then: how can Alice and Bob cook up an escape plan by communicating over the public channel in such a way that Ward doesn't suspect anything shy is going on. (Notice how steganography is dierent from classical cryptography, which is about hiding the content of secret messages: steganography is about hiding the very existence of the secret messages.) Steganographic \protocols" have a long and intriguing history that goes back to antiquity. There are stories of secret messages written in invisible ink or hidden in love letters (the rst character of each sentence can be used to spell a secret, for instance). More recently, steganography was used by prisoners and soldiers during World War II because all mail in Europe was carefully inspected at the time [9]. Postal censors crossed out anything that looked like sensitive information (e.g. long strings of digits), and they prosecuted individuals whose mail seemed suspicious. In many cases, censors even randomly deleted innocentlooking sentences or entire paragraphs in order to prevent secret messages from going through. Over the last few years, steganography has been studied in the framework of computer science, and several algorithms have been developed to hide secret messages in innocent looking data. Related Work There has been considerable work on digital steganography. The rst International Workshop on Information Hiding occurred in 1996, with ve subsequent workshops, and even books have been published about the subject [10]. Surprisingly, though, very little work has attempted to formalize steganography, and most of the literature consists of heuristic approaches: steganography using digital images [8, 10], steganography using video systems [10, 12, 18], etc. A few papers have given information theoretic models for steganography [3, 13, 15, 19], but these are limited in the same way that information theoretic cryptography is limited. We believe complexity theory is the right framework in which to view steganography and, to the best of our knowledge, this is the rst paper to treat steganography from a complexitytheoretic point of view (and to achieve provably positive results). Organization of the Paper In section 2 we dene the basic cryptographic quantities used throughout the paper, as well as the notions of a cover channel and a stegosystem. In section 3 we dene steganographic secrecy and state protocols which are steganographically secret assuming the existence of oneway functions. In section 4 we dene robust steganographic secrecy for adversaries with bounded power to perturb stegotext messages and state protocols which satisfy this denition. Section 5 closes the paper with a discussion of implications. Steganography Steganography will be thought of as a game between the warden, Ward, and the inmate, Alice. The goal of Alice is to pass a secret message to Bob over a communication channel (known to Ward). The goal of Ward is to detect whether a secret message is being passed. In this and the following sections we will formalize this game. We start by dening a communication channel. Robust Steganography Denitions for Robust Steganography Robust steganography will be modelled as a game between Alice and Ward in which Ward is allowed to make some alterations to Alice's messages. Alice wins if she can pass a message with high probability, even when Ward alters her message. For example, if Alice passes a single bit per channel message and Ward is unable to change the bit with probability at least 1 2 , Alice can use error correcting codes to reliably transmit her message. It will be important to state the limitations we impose on Ward, since otherwise he can replace all messages with a new draw from the channel distribution, eectively destroying any hidden information. In this section we give a formal denition of robust steganography with respect to a limited adversary. We will model Ward's power as dened by a relation R which is constrained to not corrupt the channel too much. This general notion of constraint is sucient to include many simpler notions such as (for example) \only alter at most 1% of the bits". Complexity theoretic ramications Construction 1 gives a stegosystem which is steganographically secret for any channel distribution C which has minimum entropy greater than 1, assuming the existence of a pseudorandom function family. Goldreich et al [5] show how to construct a pseudorandom function from a pseudorandom generator, which in turn can be constructed from any oneway function, as demonstrated by Hastad et al [6]. Thus in an asymptotic sense, our constructions show that oneway functions are sucient for steganography. Conversely, it is easy to see that a stegosystem which is steganographically secret for some C is a secure weak private key encryption protocol in the sense of Impagliazzo and Luby [7]; and they prove that the existence of such a protocol implies the existence of a oneway function. Thus the existence of secure steganography is equivalent to the existence of oneway functions. 


