A perfect maze based steganographic method

In steganography, several different types of media have been used as carriers, such as images, audios and video streams, to hide secret data. Nevertheless, various novel media and applications have been developed due to the rapid growth of internet. In this paper, we select maze games as carrier media to conceal secret data. The original idea of embedding data in a maze is proposed by Niwayama et al. Their method has two disadvantages. One is the very small embedding capacity; the other is that the stego maze is not perfect. Here, we propose an improved algorithm for increasing the embedding capacity and preserving the “perfect” property.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Asymptotically optimal perfect steganographic systems

In 1998 C. Cachin proposed an information-theoretic approach to steganography. In particular, in the framework of this approach, so-called perfectly secure stegosystems were defined, where messages that carry and do not carry hidden information are statistically indistinguishable. There was also described a universal steganographic system, for which this property holds only asymptotically, as the message length grows, while encoding and decoding complexity increases exponentially. (By definition, a system is universal if it is also applicable in the case where probabilistic characteristics of messages used to transmit hidden information are not known completely.)In the present paper we propose a universal steganographic system where messages that carry and do not carry hidden information are statistically indistinguishable, while transmission rate of “hidden” information approaches the limit, the Shannon entropy of the source used to “embed” the hidden information.     

New image steganographic methods using run-length approach

This study proposes two efficient data hiding methods incorporating both run-length encoding and modular arithmetic. The first method, BRL (hiding bitmap files by run-length), is suitable for embedding simple data with long streams of repeating bits; the second method, GRL (hiding general files by run-length), is good for embedding complicated data with short streams of repeating bits. Both of the new methods embed secret data in each nonoverlapping block composed of only two consecutive pixels, with the image quality controlled by a modular operation. In addition, the concept of run-length encoding - namely recording the number of repeating bits in the secret data and the bit value itself - is applied for simplicity and efficiency. The experimental results demonstrate that BRL and GRL have their own strengths with respect to different types of secret data. Furthermore, on the average, both can outperform other well-accepted image steganographic methods in terms of image quality and embedding capacity.     

Prediction and dimension

Given a set X of sequences over a finite alphabet, we investigate the following three quantities.

(i)

The feasible predictability of X is the highest success ratio that a polynomial-time randomized predictor can achieve on all sequences in X.

(ii)

The deterministic feasible predictability of X is the highest success ratio that a polynomial-time deterministic predictor can achieve on all sequences in X.

(iii)

The feasible dimension of X is the polynomial-time effectivization of the classical Hausdorff dimension (“fractal dimension”) of X.

Predictability is known to be stable in the sense that the feasible predictability of X∪Y is always the minimum of the feasible predictabilities of X and Y. We show that deterministic predictability also has this property if X and Y are computably presentable. We show that deterministic predictability coincides with predictability on singleton sets. Our main theorem states that the feasible dimension of X is bounded above by the maximum entropy of the predictability of X and bounded below by the segmented self-information of the predictability of X, and that these bounds are tight.     

A steganographic method based upon JPEG and particle swarm optimization algorithm

In this paper, a novel steganographic method, based on JPEG and Particle Swarm Optimization algorithm (PSO), is proposed. In order to improve the quality of stego-images, an optimal substitution matrix for transforming the secret messages is first derived by means of the PSO algorithm. The standard JPEG quantization table is also modified to contain more secret messages. The transformed messages are then hidden in the DC-to-middle frequency components of the quantized DCT coefficients of the cover-image. Finally, a JPEG file with secret messages is generated through JPEG entropy coding. We compare our algorithm with Chang et al.’s JPEG-based steganographic algorithm. The experimental results show that our proposed method has larger message capacity and better image quality than Chang et al.’s. In addition, our method also has a high security level.     

Comparing Notions of Computational Entropy

In the information theoretic world, entropy is both the measure of randomness in a source and a bound for the compression achievable for that source by any encoding scheme. But when we must restrict ourselves to efficient schemes, entropy no longer captures these notions well. For example, there are distributions with very low entropy that nonetheless look random for polynomial-bound algorithms. Different notions of computational entropy have been proposed to take the role of entropy in such settings. Results in Goldberg and Sipser (SIAM J. Comput. 20(3):524–536, 1991) and Wee (IEEE conference on computational complexity, pp. 29–41, 2004) suggest that when time bounds are introduced, the entropy of a distribution no longer coincides with the most effective compression for that source. This paper analyses three measures that try to capture the compressibility of a source, establishing relations and separations between them and analysing the two special cases of the uniform and the universal distribution m ^t over binary strings of a fixed size. It is shown that for the uniform distribution the three measures are equivalent and that for m ^t there is a clear separation between metric type entropy and the maximum compressibility of a source. Partially supported by KCrypt (POSC/EIA/60819/2004), the grant SFRH/BD/13124/2003 from FCT and funds granted to LIACC through the Programa de Financiamento Plurianual, FCT and Programa POSI.     

A high stego-image quality steganographic scheme with reversibility and high payload using multiple embedding strategy

Tian’s method is a breakthrough reversible data embedding scheme with high embedding capacity measured by bits per pixel (bpp) and good visual quality measured by peak signal-to-noise ratio (PSNR). However, the embedding capacity and visual quality of this method can be significantly improved. Thus, we propose a simple reversible steganographic scheme in spatial domain for digital images by using the multiple embedding strategy. The proposed method horizontally and vertically embeds one secret bit into one cover pixel pair. The experimental results show that the proposed reversible steganographic method achieves good visual quality and high embedding capacity. Specifically, with the one-layer embedding, the proposed method can obtain the embedding capacity of more than 0.5 bpp and the PSNR value greater than 54 dB for all test images. Especially, with the five-layer embedding, the proposed method has the embedding capacity of more than 2 bpp and the PSNR value higher than 52 dB for all test images. Therefore, the proposed method surpasses many existing reversible data embedding methods in terms of visual quality and embedding capacity.     

Image registration by compression

Image registration consists in finding the transformation that brings one image into the best possible spatial correspondence with another image. In this paper, we present a new framework for image registration based on compression. The basic idea underlying our approach is the conjecture that two images are correctly registered when we can maximally compress one image given the information in the other. The contribution of this paper is twofold. First, we show that image registration can be formulated as a compression problem. Second, we demonstrate the good performance of the similarity metric, introduced by Li et al., in image registration. Two different approaches for the computation of this similarity metric are described: the Kolmogorov version, computed using standard real-world compressors, and the Shannon version, calculated from an estimation of the entropy rate of the images.     

Reversible steganographic method using SMVQ approach based on declustering

Reversible steganography allows an original image to be completely restored after the extraction of hidden data embedded in a cover image. In this paper, we propose a reversible scheme for VQ-compressed images that is based on a declustering strategy and takes advantage of the local spatial characteristics of the image. The main advantages of our method are ease of implementation, low computational demands, and no requirement for auxiliary data. The experimental results show that the embedding capacity of the proposed method is controlled by the number of declustered groups and the spatial characteristics of the cover image. The results also show that the proposed method has the best embedding capacity and the least running time compared with other methods.     

Conditional entropy for incomplete decision systems and its application in data mining

Rough set theory is a useful mathematic tool for dealing with vague and uncertain information. Shannon's entropy and its variants have been applied to measure uncertainty in rough set theory from the viewpoint of information theory. However, few studies have been carried out on information-theoretical measure of attribute importance in incomplete decision system (IDS) considering the relation between decision attribute and condition attributes. In this paper, we introduce the concept of conditional entropy together with entropy and joint entropy in IDSs. By using the new conditional entropy, we propose a measure for attribute importance. Based on the measure, a heuristic attribute reduction algorithm is presented. Some test experiments on real-lift data-sets show the effectiveness of the algorithm. The attribute importance measure and the attribute reduction algorithm can be used in data mining or machine learning for handling incomplete data.     

Studying software evolution using artefacts’ shared information content

In order to study software evolution, it is necessary to measure artefacts representative of project releases. If we consider the process of software evolution to be copying with subsequent modification, then, by analogy, placing emphasis on what remains the same between releases will lead to focusing on similarity between artefacts. At the same time, software artefacts-stored digitally as binary strings-are all information. This paper introduces a new method for measuring software evolution in terms of artefacts’ shared information content. A similarity value representing the quantity of information shared between artefact pairs is produced using a calculation based on Kolmogorov complexity. Similarity values for releases are then collated over the software’s evolution to form a map quantifying change through lack of similarity. The method has general applicability: it can disregard otherwise salient software features such as programming paradigm, language or application domain because it considers software artefacts purely in terms of the mathematically justified concept of information content. Three open-source projects are analysed to show the method’s utility. Preliminary experiments on udev and git verify the measurement of the projects’ evolutions. An experiment on ArgoUML validates the measured evolution against experimental data from other studies.     

A history of graph entropy measures

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.     

Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers

We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and wherethey are fundamentally different. We discuss and relate the basicnotions of both theories: Shannon entropy, Kolmogorov complexity, Shannon mutual informationand Kolmogorov (``algorithmic') mutual information. We explainhow universal coding may be viewed as a middle ground betweenthe two theories. We consider Shannon's rate distortion theory, whichquantifies useful (in a certain sense) information.We use the communication of information as our guiding motif, and we explain howit relates to sequential question-answer sessions.     

A new steganographic method for color and grayscale image hiding

In this paper, we present a steganographic method for embedding a color or a grayscale image in a true color image. Three types of secret images can be carried by the proposed method: hiding a color secret image, hiding a palette-based 256-color secret image, and hiding a grayscale image in a true color image. Secret data are protected by the conventional crypto system DES. We compare the image quality and hiding capacity of the proposed method with those of the scheme in Lin et al.’s scheme. According to the experimental results, the image quality of the proposed method is better than that of the Lin et al.’s scheme. In addition, annotation data can be hidden with the secret image in the host image. The hiding capacity of the proposed method is greater than that of other compared schemes. The experimental results show that the proposed method is a secure steganographic method that provides high hiding capacity and good image quality.     

A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems

In 2002, Jurdziński and Lory? settled a long-standing conjecture that palindromes are not a Church-Rosser language. Their proof involved a difficult analysis of computation graphs associated with 2-pushdown-stack automata. We present a shorter and easier proof in terms of 1-tape Turing machines.We also discuss how the proof generalises to almost-confluent Thue systems and the differing powers of Church-Rosser, almost-confluent, and preperfect Thue systems in relation to palindromes.     

A high quality steganographic method with pixel-value differencing and modulus function

In this paper, we shall propose a new image steganographic technique capable of producing a secret-embedded image that is totally indistinguishable from the original image by the human eye. In addition, our new method avoids the falling-off-boundary problem by using pixel-value differencing and the modulus function. First, we derive a difference value from two consecutive pixels by utilizing the pixel-value differencing technique (PVD). The hiding capacity of the two consecutive pixels depends on the difference value. In other words, the smoother area is, the less secret data can be hidden; on the contrary, the more edges an area has, the more secret data can be embedded. This way, the stego-image quality degradation is more imperceptible to the human eye. Second, the remainder of the two consecutive pixels can be computed by using the modulus operation, and then secret data can be embedded into the two pixels by modifying their remainder. In our scheme, there is an optimal approach to alter the remainder so as to greatly reduce the image distortion caused by the hiding of the secret data. The values of the two consecutive pixels are scarcely changed after the embedding of the secret message by the proposed optimal alteration algorithm. Experimental results have also demonstrated that the proposed scheme is secure against the RS detection attack.     

一种基于数字密写的信息安全传输方案设计

在信息安全传输领域,为弥补密码技术的不足,在分析功能要求的基础上,提出了压缩软件、加密软件和密写软件相结合的信息安全传输方案,给出方案的详细处理过程,并重点设计了密写软件,对其嵌入部分和提取部分的实现过程分别进行了设计说明。实验表明,该方案切实可行,安全性较只使用加密技术有所提高。