Steganography combining data decomposition mechanism and stegocoding method.
A novel steganographic scheme based on data decomposition decomposition /de·com·po·si·tion/ (dekom?pahzish´un) the separation of compound bodies into their constituent principles. de·com·po·si·tion n. 1. and stegocoding mechanisms is proposed. In this" scheme, a secret message is represented as a sequence of digits in a notational system with a prime base. Each digit block is decomposed de·com·pose v. de·com·posed, de·com·pos·ing, de·com·pos·es v.tr. 1. To separate into components or basic elements. 2. To cause to rot. v.intr. 1. into a number of shares. By using stegocoding technique, these shares are then embedded Inserted into. See embedded system. in different cover images respectively. In each cover, a share is carried by a group of cover pixels and, at most, only one pixel in the group is increased or decreased by a small magnitude. That implies a high embedding 1. (mathematics) embedding  One instance of some mathematical object contained with in another instance, e.g. a group which is a subgroup. 2. (theory) embedding  (domain theory) A complete partial order F in [X > Y] is an embedding if efficiency, and therefore distortion introduced to the covers is low, leading to enhanced imperceptibility im·per·cep·ti·ble adj. 1. Impossible or difficult to perceive by the mind or senses: an imperceptible drop in temperature. 2. of the secret message. A further advantage of the scheme is that, even a part of stegoimages are lost during transmission, the receiver can still extract embedded messages from the surviving covers. Keywords: steganography, data decomposition, embedding efficiency Povzetek: Predstavljena je nova steganografska metoda. 1 Introduction Steganography is a branch of information hiding Keeping details of a software routine (function or object) private. Programmers only know what input is required and what outputs are expected. See encapsulation and abstraction. that aims to send secret messages under the cover of a carrier signal. While many steganographic methods have been proposed for various types of cover media in recent years, techniques of steganalysis have also rapidly developed to detect the presence of secret messages based on statistical abnormality abnormality /ab·nor·mal·i·ty/ (ab?normal´ite) 1. the state of being abnormal. 2. a malformation. ab·nor·mal·i·ty n. caused by data hiding (1) Secretly embedding data in graphics images and other file types. See steganography. (2) The result of encapsulation in objectoriented programming. See encapsulation. [1, 2]. Generally speaking, the more the embedded data, the more vulnerable the system will be to the steganalytic attempts. When a multimedia product is under suspicion, the channel warden WARDEN. A guardian; a keeper. This is the name given to various officers: as, the warden of the prison; the wardens of the port of Philadelphia; church wardens. may refuse to transmit it, and the source of the message can be tracked. As a countermeasure coun·ter·meas·ure n. A measure or action taken to counter or offset another one. countermeasure Noun action taken to counteract some other action Noun 1. , the datahider always tries to improve statistical imperceptibility of the hidden message. An important technique to improve imperceptibility is to reduce the amount of alterations to be introduced into the cover for hiding the same quantity of data, in other words Adv. 1. in other words  otherwise stated; "in other words, we are broke" put differently , to improve embedding efficiency. For example, Matrix encoding See encode. uses less than one change of the least significant bit (LSB (Linux Standard Base) A standard interface (ABI) for Linux from the Linux Foundation (www.linuxfoundation.org). Introduced in 2001 by the Free Standards Group, which later became the Linux Foundation, applications based on the LSB standard will run properly under ) in average to embed em·bed also im·bed v. em·bed·ded, em·bed·ding, em·beds v.tr. 1. To fix firmly in a surrounding mass: embed a post in concrete; fossils embedded in shale. I bits into [2.sup.l]1 pixels [3]. In this way, distortion is significantly lowered compared to a plain LSB technique in which secret bits simply replace the LSB. Further, some effective encoding methods derived from the cyclic cyclic /cyc·lic/ (sik´lik) pertaining to or occurring in a cycle or cycles; applied to chemical compounds containing a ring of atoms in the nucleus. cy·clic or cy·cli·cal adj. 1. coding have been described [4], and the matrix encoding can be viewed as a special case. In [5], two methods based on random linear codes and simplex codes are developed for large payloads. Another method, termed running coding, can also be performed on a data stream derived from the host in a dynamically running manner [6]. All the abovementioned stegocoding techniques are independent of any particular coverbitmodification approaches. For example, if a stegocoding method is used in the LSB plane of an image, adding 1 to a pixel is equivalent to subtracting 1 from the pixel to flip its LSB for carrying the secret message. In addition, we [7] and Fridrich et al. [8] independently presented a same method with better performance, termed respectively exploiting modification direction (EMD EMD Electromechanical dissociation, see there ) and grid coloring (GC for short). Using this method, [log.sub.2](2q+l) secret bits are embedded into q cover pixels and, at most, only one pixel is increased or decreased by 1. In [8], a datahiding approach incorporating GC with Hammingderived steganographic encoding technique is also studied, which in fact is a special case of GC. We also applied the wet paper codes to steganography to further increase embedding efficiency [9, 10 11]. Since stegocovers may be lost due to an active warden or poor channel conditions, a steganographic system capable of resisting interference is also desired to the datahider. This paper proposes a novel steganographic scheme by introducing a data decomposition mechanism together with stegocoding techniques, such as running coding and EMD embedding methods. In this way, the secret message is inserted into a number of cover images with high embedding efficiency. Even a part of stegoimages are missing, one can still extract the hidden message from the remaining covers. The rest of this paper is organized as follows. Section 2 introduces the related stegocoding methods. The proposed scheme is described in Section 3 and 4. Then, the experimental results are shown in Section 5. Finally, we conclude in Section 6. 2 Related Stegocoding methods In stegocoding methods, a number of patterns of cover data are used to represent a type of secret data, and the datahider modifies the original cover data to the nearest pattern mapping the secret data to be hidden. This way, by changing a small part of cover data, a fairly large amount of secret data can be embedded. In this section, we briefly review the related techniques including running coding and EMD embedding methods. 2.1 Running coding With running coding method [6], each secret bit is represented by a series of consecutive cover bits, and each available cover bit also relates to several consecutive secret bits. In other words, the secret message is embedded as a data stream, and each coverbitalteration is used to embed several consecutive secret bits. Assume that the secret message to be hidden contains K bits: [[x.sub.1,] [x.sub.2,] ..., [x.sub.K], and the available LSB for carrying the secret message are [b.sub.1,1], [b.sub.1,2]. ..., [b.sub.1,T]; [b.sub.2,1], [b.sub.2,2], ..., [b.sub.2,T]; ...; [b.sub.K,1], [b.sub.K,2], ..., [b.sub.K,T]], where T is an integer integer: see number; number theory power of 2 (T = [2.sup.t]). A binary generating matrix G sized (t+l) x T is first constructed. Denote de·note tr.v. de·not·ed, de·not·ing, de·notes 1. To mark; indicate: a frown that denoted increasing impatience. 2. the elements in G as g(i,j), where i [less than or equal to] i [less than or equal to] t+l and 1 [less than or equal to] j [less than or equal to] T. Assign all the elements in the first row as '1' and make all the 2' columns in G mutually different. For example, the generating matrix of the 4th running coding is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII ASCII or American Standard Code for Information Interchange, a set of codes used to represent letters, numbers, a few symbols, and control characters. Originally designed for teletype operations, it has found wide application in computers. ] (1) According to according to prep. 1. As stated or indicated by; on the authority of: according to historians. 2. In keeping with: according to instructions. 3. the original host data and the generating matrix G, calculate [y.sub.v] [t+l.summation summation n. the final argument of an attorney at the close of a trial in which he/she attempts to convince the judge and/or jury of the virtues of the client's case. (See: closing argument) over (i=1)] [T.summation over (j=1)] [g(i, j) x [b.sub.vi+l,j]] mod 2, v=1, 2, ..., K (2) where [b.sub.vi+l,j = 0] if vi+1 [less than or equal to] 0. The datahider can use a small number of alterations in these host bits to make the values of [y.sub.v]s equal to the secret bits [x.sub.v]s. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3) Orderly arrange all [x.sub.v]s to form a vector Z = [[z.sub.1,] [z.sub.2], ..., [[z.sub.X]].sup.T], and divide Z into a set of subvectors in the following way: 1. Scan the vector Z from the beginning to the end; 2. If the encountered bit is '0', define this '0' as a subvector containing only one element; 3. If the bit is '1', define this '1' together with the following t bits as a subvector with a length (t+1). Obviously, the subvector in this case must be identical to one of the columns in G. That means Z is segmented into a sequence of subvectors, each being either a column of the generating matrix G or a single zero. According to (2), flipping the value of host bit [b.sub.v,j] will change the value of [y.sub.v+i1] if g(i, j)=1 (1 [less than or equal to] i [less than or equal to] t+1, 1 [less than or equal to] j [less than or equal to] T). Thus, we can modify only one host bit to change the values of several [y.sub.v]s. Assume that a subvector [[z.sub.v,] [[z.sub.v+1], ..., [z.sub.v+t].sup.T] is same as the jth column of G. By flipping the value of host bit [b.sub.v,j,] the datahider may make [[y'.sub.v], [y'.sub.v+1], ..., [y'.sub.v+t] identical to [[x.sub.v], [x.sub.v+1], ...., [x.sub.v+1], where [[y'.sub.v], [y'.sub.v+1], ..., [y'.sub.v+t]] are obtained from the modified host bits according to (2). This way, the secret data can be embedding using a small number of bitalterations. 2.2 EMD embedding EMD embedding [7] is an alternative method for inserting secret data into a certain cover image with a high embedding efficiency. Using this method, each symbol in notational system with an odd base will be carried by a group of pixels, and, at most, only one pixel is increased or decreased by 1. Denote a secret symbol in notational system with an odd base (2q+l) as s, and the gray values of pixels in a group as [g.sub.1,] [g.sub.2,] ..., [g.sub.q.] Calculate the extraction function f as a weighted sum modulus See modulo. (2q+l) f([g.sub.1,] [g.sub.2, ..., [g.sub.q]) = [q.summation over (i=1]) mod (2q + 1) (4) Consider the vector [[g.sub.1,] [g.sub.2], ..., [g.sub.q]] as a hypercube in qdimensional space. The extraction function must have the following two properties: 1) values of the extraction function on all hypercubes fall in the interval [0 2q], and 2) the values off on any hypercube and its 2q neighbors are mutually different. This implies that a symbol in the (2q+l)ary notational system can be carried by a pixelgroup, and, at most, only one pixel will be increased or decreased by 1. If the symbol s equals the extraction function of the original corresponding pixelgroup, no modification is needed. When s [not equal to]f, calculate u = s f rood rood (rd), crucifix mounted above the entrance to the chancel and flanked by large figures of the Virgin and St. p. If u is no more than q, increase the value of [g.sub.u] by 1, otherwise, decrease the value Of [g.sub.pu] by 1. For example, considering an original pixelgroup [137 139 141 140] with q = 4, f = 3 and a corresponding symbol 4 in 9ary notational system, a datahider can calculate u = 1, so he can increase the gray value of the first pixel by 1 to produce the stegopixels [138 139 141 140]. If the symbol to be hidden is 0, u = 8 can be calculated and the gray value of the forth pixel will be decrease by 1 to yield [137 139 141 139]. 3 Data embedding procedure In this proposed scheme, a secret message is firstly represented as a series of shares according to a data decomposition mechanism and various indices, and the shares corresponding to different indices are respectively inserted into different cover images. Then, a generalized running coding or EMD method is employed to keep stegoinduced distortion at a low level, and redundancy in the shares ensures that one can recover the original secret message from a part of stegocovers. 3.1 Data decomposition At the beginning, a datahider converts a secret message into a digit sequence in a notational system with an odd and prime base p, such as 3, 5, 7, 11, etc. If the secret message is a binary stream, it can be segmented into many pieces, each having [L.sub.1] bits, and the decimal Meaning 10. The numbering system used by humans, which is based on 10 digits. In contrast, computers use binary numbers because it is easier to design electronic systems that can maintain two states rather than 10. value of each secret piece is represented by [L.sub.2] digits in a pary notational system, where [L.sub.1] = [[L.sub.2] x [log.sub.2] p] (5) For example, the binary message (1001 1101 0110) can be rewritten as (14 23 11) in 5ary notational system when [L.sub.1] = 4 and [L.sub.2] = 2. Thus, the rate of redundancy in the digit sequence [R.sub.R] = 1  [L.sub.1]/[L.sub.2] x [log.sub.2]p < 1/[L.sub.1] + 1 (6) With large [L.sub.1] and [L.sub.2], [R.sub.R] is very close to 0, therefore can be ignored. So, the secret message is regarded as a digit sequence in pary notational system in the following discussion. Then, the datahider segments the secret digit sequence into a series of blocks, each of which contains m digits. Denote the number of blocks as K, and the block as {[d.sub.k,1], [d.sub.k,2], ..., [d.sub.k, m]} (k = 1, 2, ..., K). Inspired by [12], decompose de·com·pose v. de·com·posed, de·com·pos·ing, de·com·pos·es v.tr. 1. To separate into components or basic elements. 2. To cause to rot. v.intr. 1. each secret block into n shares, {[s.sub.k, 1], [s.sub.k,2], ..., [s.sub.k,n]}, in the following way, [[S.sub.k,1] [S.sub.k,2] ... [S.sub.k,n]]=[[d.sub.k,1] [d.sub.k,2] ... [d.sub.k,m]] x A (7) where m [less than or equal to] n [less than or equal to] p, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8) and the symbol "." in (7) is a multiplication operator with a modulus p. We call [a.sub.1,] [a.sub.2,] ..., and [a.sub.n] as indices. All indices lie between [0 pl] and are mutually different. For example, assuming p = 5, n = 4, m = 3, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9) a digit block {2, 4, 1} can be represented as 4 shares: 4, 4, 2, and 2. Note that the shares are also within the pary notational system. Collect all shares and divide them into n sets {[s.sub.1,1,], [s.sub.2,1], ..., [s.sub.K,1]}, {[s.sub.1,2], [s.sub.2,2], ..., [S.sub.K,2]}, ..., {[S.sub.1,n], [s.sub.2,n], ..., [s.sub.K,n]}, each of which contains K shares. Then, the n sharesets and their corresponding indices will be embedded into n cover images, respectively. Since the indices are within [0 p1], they can also be regarded as symbols in the pary notational system. In other words, each cover image will be used to conceal conceal, v to hide; secrete; withhold from the knowledge of others. (K+1) symbols in the pary notational system, [s.sub.1,t], [s.sub.2,t], ..., [s.sub.K,t] and [a.sub.t] (t = 1, 2, ..., n). 3.2 Generalized running coding In order to improve steganographic imperceptibility, we use stegocoding technique to lower the distortion caused by data embedding. As mentioned above, running coding in [6] is only suitable for binary datahiding system. This subsection subsection Noun any of the smaller parts into which a section may be divided Noun 1. subsection  a section of a section; a part of a part; i.e. generalizes the running coding method, so that the secret symbols in the pary notational system can be carried by a sequence of graypixelvalue of cover image. Actually, for each cover image, either generalized running coding or EMD embedding can be employed to embed the shares and index. In the generalized running coding method, each secret symbol in the pary notational system is represented by a series of consecutive cover values, and each cover value also relates to several consecutive secret symbols. Thus, a datahider can modify a selected cover value to embed several secret symbols, so that the distortion introduced into the cover signal is significantly reduced, which also means the datahiding efficiency is increased. For convenience, we denote the (K+1) symbols in the pary notational system to be embedded into a certain cover as [[X.sub.1,] [x.sub.2,] ..., [x.sub.K+1]]. Pseudorandomly select (K+1) x T pixels in cover image according to a secret key, and denote the graylevels of them as [[h.sub.1,1], [h.sub.1,2], ..., [h.sub.1, k+1]; [h.sub.2,1], [h.sub.2,2], ..., [h.sub.2,k+1]; ...; [h.sub.T,1], ..., [h.sub.T, k+1]. That means the number of host values is T times of that of secret symbols. 3.2.1 The case of T = [p.sup.t] Firstly, we discuss the case that T is an integer power of p (T = [p.sup.t]). Inspired from [6], construct a generating matrix G sized (t+l) x T. Denote the elements in G as g(i, j), and assign them according to the following principle, 1. All elements are integers within [0, p1]. 2. All elements in the first row are 1. 3. All [p.sup.t] columns in G are different. For example, when p=3 and k=9, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10) From the original host data and the generating matrix G, calculate [y.sub.v] = [t + 1.summation over (i = 1)][T.summation over (j = 1)][g(i, j) x [h.sub.v  i + 1, j]] mod p, v = 1, 2, ..., K + 1 (11) where [h.sub.vi + 1,j] = 0 if vi + 1 [less than or equal to] 0. That means the value of [y.sub.v] is determined by (t + 1) x T host values [h.sub.v  t,1], [h.sub.v  t,2], ..., [h.sub.v  t,T], [h.sub.v  t + 1,1,] [h.sub.v  t + 1,2], ..., [h.sub.v  t + 1,T], ..., [h.sub.v,1,] [h.sub.v,2], ... [h.sub.v,]T. Similarly, we will modify a small number of host values to make each [y.sub.v] equal to the corresponding secret [x.sub.v.] Let [z.sub.v] = [x.sub.v]  [y.sub.v] mod p, v = 1, 2, ..., K + 1 (12) Arrange all the [z.sub.v] to form a vector Z = [[[z.sub.1], [z.sub.2], ..., [z.sub.K + 1]].sup.T], and then divide Z into a set of subvectors in the following way: 1. Scan the vector Z from the beginning to the end; 2. If the encountered digit is '0', define this '0' as a subvector containing only one element; 3. If the encountered digit [z.sub.v] is not '0', define this digit together with the following t digits as a subvector with a length (t + 1). Because all the elements in the first row of G are 1 and p is prime, the subvector in this case must be equal to product of [z.sub.v] and one of the columns in G with modulus p. Equation (11) indicates that any change on host value [h.sub.vj] will affect the values of [y.sub.v], [y.sub.v + 1], ..., [y.sub.v + t] . Thus, we can modify only one host value but embed several secret symbols. Assume that [z.sub.v] is not 0 and the subvector [[[z.sub.v], [z.sub.v + 1], ..., [z.sub.v + t]].sup.T] equals the product Of [z.sub.v] and the jth column of G with modulus p. Either increasing the value of [h.sub.v,j] by [z.sub.v] or decreasing the value of [h.sub.v,j] by p[z.sub.v] will make [[y'.sub.v], [y'.sub.v + 1], ..., [y'.sub.v + t]] identical to [[x.sub.v], [x.sub.v + 1], ..., [x.sub.v + t]], where [[y'.sub.v], [y'.sub.v + 1], ..., [y'.sub.v + t]] are obtained from the modified host values according to (11). In this way, all secret symbols can be embedded by performing the similar operation for all subvectors. Consider that, for example, a host value sequence with length 21 for carrying secret message is [40 187 99, 93 231 19, 82 78 33, 11 176 134, 56 27 121, 31 249 83, 90 111 24], and 7 secret digits in ternary (programming) ternary  A description of an operator taking three arguments. The only common example is C's ?: operator which is used in the form "CONDITION ? EXP1 : EXP2" and returns EXP1 if CONDITION is true else EXP2. system, implying p = 3, [2110100]. Because T = 21/7 = [3.sup.1], construct a generating matrix G. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13) From (11), the vector Y is [2200021], so that Z = [[0210112].sup.T]. Append To add to the end of an existing structure. '0' to the end of Z and segment it into 5 subvectors: [0], [[21].sup.T], [0], [[11].sup.T], and [[20].sup.T]. Note that appending ' 1' or '2' is also allowable. Since the subvector [[21].sup.T] is a product of 2 and the 3rd column of G with modulus 3, the datahider should increase [h.sub.2,3] by 2 or decrease [h.sub.2,3] by 1. To lower the distortion, the value of [h.sub.2,3] is decreased by 1. Similarly, h5,2 should be increased by 1, and [h.sub.7,1] decreased by 1. So, the stegosequence [40 187 99, 93 231 18, 82 78 33, 11 176 134, 56 28 121, 31 249 83, 89 111 24] are produced. In this way, 7 symbols in ternary system are embedded by adding/subtracting 1 to/from three pixels. On the receiving side, a simple calculation of (11) can recover the embedded data, when the receiver knows the values of p, T and G. A ratio between the number of embedded bits and the distortion energy caused by data hiding, E, is used to indicate the embedding efficiency. As mentioned above, a subvector must be '0', or contains (t + 1) elements and begins with a nonzero digit. Since the values of z are also uniformly distributed within [0, p  1], the probability of the former case is 1/p, while that of the later case is (p  1)/p. In the former case, the secret symbol has been represented and any modification is needless, while in the later case, a modification on one host value is made to embed (t + 1) digits. In average, (p x t  t + p)/p secret symbols are embedded by modifying (p1)/p host values. As p is odd, the modifications on host values are within [(1  p)/2, (p  1)/2], thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14) which is significantly larger than 2, the embedding efficiency of plain LSB replacement/matching method. 3.2.2 The case of [p.sup.t] < T< [p.sup.t + 1] If T is not an integer power of p, i.e., [p.sup.t] < T < [p.sup. t + 1], a generating matrix G sized (t + 2) x T can also be constructed as follows: 1. All elements are integers within [0, p1]. 2. All elements in the first row are 1. 3. All g(t + 2, j) are 0 where 1 [less than or equal to] j [less than or equal to] [p.sup.t]. 4. The columns in G are different. For instance, when p=5 and T=8, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15) Similarly, [y.sub.s] and [z.sub.s] can be computed from (11) and (12). Vector Z can be segmented into subvectors in the following way: 1. Scan the vector Z from the beginning to the end; 2. If the encountered digit is 0, designate des·ig·nate tr.v. des·ig·nat·ed, des·ig·nat·ing, des·ig·nates 1. To indicate or specify; point out. 2. To give a name or title to; characterize. 3. this digit as a subvector and denote this type of subvector as [SV.sub.0]; 3. If the encountered digit [z.sub.v] is not 0, and the vector containing [z.sub.v] and the following (t + 1) digits is equal to a product of [z.sub.v] and one of the columns in G with modulus p, designate the (t + 2) digits as a subvector, and denote this type of subvector as [SV.sub.1]; 4. If the encountered digit [z.sub.v] is not 0, and the vector containing [z.sub.v] and the following (t + 1) digits is not the same as the product of [z.sub.v] and any column in G with modulus p, designate [z.sub.v] and the following t digits as a subvector with length (t + 1), and denote this type of subvector as [SV.sub.2] . In this case, the next subvector must start with a nonzero digit. Denoting the upleft submatrix of G sized (t + 1) x [p.sup.t] as G', an [SV.sub.2] subvector must be equal to a product of [z.sub.v] and one of the columns in G' with modulus p. For an [SV.sub.0] subvector, no modification is needed. But for an [SV.sub.1] subvector equal to a product of its first element [z.sub.v] and the jth column in G with modulus p or an [SV.sub.2] subvector equal to a product of its first element [z.sub.v] and the jth column in G' with modulus p, the datahider should increase the value of [h.sub.v,j] by [z.sub.v] or decrease it by p[z.sub.v]. For example, consider 80 host values available for carrying secret message and 10 secret symbols in 5ary notational system [2314023343]. Because T = 80/10 = 8, we can construct a generating matrix G as in (14). Assuming the vector Y = [2130204131] can be calculated according to (11), thus Z = [[0234324212].sup.T]. Append a '0' to the end of Z and segment it into 5 subvectors [0], [[23].sup.T], [[43].sup.T], [[242].sup.T], and [[120].sup.T] . Following the rule of modification as described above, the datahider should increase [h.sub.2,5] by 2, decrease [h.sub.4,3] by 1, increase [h.sub.6,8] by 2, and increase [h.sub.9,3] by 1 so as to embed the secret data. Now we calculate the embedding efficiency. As mentioned, a subvector following an [SV.sub.2] must be [SV.sub.1] or [SV.sub.2]. Therefore, any sequence of subvectors between the end of an [SV.sub.1] and the end of the next [SV.sub.1] must be in the form of {0, 0, ..., 0, [SV.sub.2], [SV.sub.2], ..., [SV.sub.2], [SV.sub.1]}. Denote the numbers of consecutive 0s and [SV.sub.2] subvectors as [l.sub.0] and [l.sub.2] ([l.sub.0], [l.sub.2] = 0, 1, 2, ...), respectively. In the above example, the pattern of the first 4 subvectors is {0, [SV.sub.2], [SV.sub.2], [SV.sub.1]} ([l.sub.0] = 1, [l.sub.2] = 2). Denoting [eta] = T/[p.sup.t + 1] (16) the probability of a subvector sequence with [l.sub.0] '0's, [l.sub.2] [SV.sub.2] subvectors, and an [SV.sub.1] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17) For the subvector sequence, a total of [[l.sub.0] + [l.sub.2] x (t + 1) + t + 2] secret digits are embedded by modifying (l2+1) host values. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18) 3.3 Application of EMD embedding When using EMD embedding for concealing (K + 1) pary symbols, including K shares and an index, into a cover image, pseudorandomly select (K + 1).q pixels according to a secret key, and divide them into (K + 1) pixelgroups, each of which contains q pixels. Here, q = p  1/2 (19) Then, we map the (K + 1) symbols to the pixelgroups in a onebyone manner. Using EMD embedding method, each symbol in the pary notational system is carried by a group of pixels, and, at most, only one pixel is increased or decreased by 1. As analysed in [7], the embedding efficiency is E = p x [log.sub.2] p/p  1 (20) which is also significantly larger than 2, the embedding efficiency of plain LSB replacement/matching method. Note that both generalized running coding method and EMD embedding method can be used to gain a high embedding efficiency, and the stegocoding techniques used in different covers may be different. So, an additional bit that labels the stegocoding technique used in a certain cover, e.g., '0' for generalized running coding and' 1' for EMD embedding, as well as the values of p and K, should be embedded into the cover image itself. If running coding is executed, the parameter T should be also hidden in the corresponding stegoimage. Actually, LSB replacement method can be used to embed the additional secret information into cover images, and the embedding positions may be determined by the secret key. 4 Data extracting procedure As mentioned in the previous section, the secret message is embedded into n cover images, and all the n stegoimages are sent through a poor channel. Assume the stegoimages may be lost in the channel. If the number of received stegoimages is no less than m, one can still recover the original secret message using m arbitrary stegoimages. For each received stegoimage, the receiver first extracts the embedded labelbit of stegocoding technique and the values of parameter p, K and T. If generalized running coding is used in the cover, the receiver selects (K + 1) x T pixels according to the same secret key, and calculates the K embedded shares, [s.sub.1,t], [s.sub.2,t], ..., [s.sub.K,t], and the embedded index at (t = 1, 2, ..., n) using (11). If EMD method is used, the receiver selects (K + 1) x q pixels according to the same secret key, and divides them into (K + 1) pixelgroups. Then, he calculates the extraction function of stegopixelgroups to obtain the (K + 1) embedded symbols. This way, the receiver may extract a total of K x m shares and m indices from m received stegoimages. Denote the extracted indices as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For each digit block, Equation (7) can be reformulated as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21) The left side is m shares extracted from different stegoimages, and [A.sub.t] is an m x m matrix made up of m columns of A corresponding to the extracted indices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22) As well known, [A.sub.t] is a Vandermonde matrix In linear algebra, a Vandermonde matrix, named after AlexandreThéophile Vandermonde, is a matrix with a geometric progression in each row, i.e; [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23) Since all at are mutually different, [absolute value of [A.sub.t] can not be zero. That means [A.sub.t] must have an inverse (mathematics) inverse  Given a function, f : D > C, a function g : C > D is called a left inverse for f if for all d in D, g (f d) = d and a right inverse if, for all c in C, f (g c) = c and an inverse if both conditions hold. with the modulus p, [A.sup.1.sub.t] = [A.sup.*.sub.t]/[absolute value of [A.sub.t]] (24) where [A.sup.*.sub.t] is the adjoint Ad´joint n. 1. An adjunct; a helper. matrix of [A.sub.t]. So, the secret digit block can be restored by using m extracted shares and the inverse matrix of [A.sub.t] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (25) For example, for the matrix A in Equation (9), the indices extracted from three stegoimages are 2, 4, and 1, the receiver can obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (26) and its inverse [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (27) If the three extracted shares are respectively 4, 4, and 2, the digit block is then calculated [4 2 2] x [A.sup.1.sub.t] = [2 4 1] (28) After calculating all the digit blocks, the receiver can concatenate To link structures together. Concatenating files appends one file to another. In speech synthesis, units of speech called "phonemes" (k, sh, ch, etc.) are concatenated to produce meaningful sounds. them to retrieve the secret message. 5 Experiment results In the experiment, a secret message with 3.6 x [10.sup.5] bits was first converted into 1.3 x [10.sup.5] digits in 7ary notational system. After segmenting the secret digit sequence into a series of blocks with length 4, each digit block was decomposed into 6 shares using Equation (7). That means p = 7, n = 6, and m = 4. Then, the 6 sharesets and their corresponding indices were embedded into 6 cover images sized 512 x 512. In other words, each cover image was used to conceal 3.2 x [10.sup.4] symbols in 7ary notational system. Then, we produced 6 stegoimages, three of them produced by using generalized running coding with T = 8, and the rest three by using EMD method. Figure 1 shows 4 stegoimages among them. In each stegoimage produced by generalized running coding, the number of changed pixels was 1.5 x [10.sup.4] with the modifications within [3, 3], and the value of PSNR PSNR Peak SignaltoNoise Ratio PSNR Peak Signal to Noise Rate due to data hiding is 53.9 dB, indicating the visual imperceptibility. In each stegoimage produced by EMD method, there were 2.8 x [10.sup.4] pixels increased/decreased by 1, and the value of PSNR is 57.8 dB. Since only a small part of cover pixels were increased or decreased by small magnitudes, it is difficult to detect the presence of secret message. Actually, if one receives no less than four stegoimages among all the six, he can always recover the secret message using the data extracted from the received stegoimages. We also attempted to conceal the same secret message using various steganographic methods, respectively. With a plain LSB embedding method, two cover images with a size of 512 x 512 were required to provide sufficient LSBs for accommodating the secret data. In this case, the values of PSNR of the stegoimages are 52.1 dB. When employing the original running coding and assigning the parameter T = 2, the secret message were carried by three 512 x 512 cover images with PSNR 52.9 dB. Alternatively, after converting the secret message into a series of 7ary symbols (q = 3), we exploited EMD embedding method to conceal them into four cover images. Here, PSNR due to datahiding is 57.8 dB. When the three methods are used, all stegoimages are necessary for data extraction Data extraction is the act or process of retrieving (binary) data out of (usually unstructured or badly structured) data sources for further data processing or data storage (data migration). at receiver side. Table 1 shows the performance comparison between the three methods and the proposed scheme. Note that, although the proposed scheme exploits more cover images, the steganographic distortion is lower and the secret message can be transmitted through a severe channel. [FIGURE 1 OMITTED] 6 Conclusion In the proposed steganographic scheme, a data decomposition mechanism is introduced to represent the secret message as a number of share sets, and both generalized running coding and EMD embedding methods can be employed to embed the shares into different cover images with high efficiency. This way, even though a part of stegoimages are lost in a severe channel, one can still recover the hidden message from the received covers. Two aspects deserve further study in the future. One is error correcting capability of the proposed scheme. In many applications, the receiver may obtain most stegoimages with channel noise. Since there is redundancy between the sharesets embedded into different covers, the receiver can still restore the secret message when the noise is not too serious. On the other hand, since it is necessary to distribute the payloads into cover images according to their various sizes, a technique for decomposing the secret message into sharesets with different amounts is desired, i.e., a generalization gen·er·al·i·za·tion n. 1. The act or an instance of generalizing. 2. A principle, a statement, or an idea having general application. of the datadecomposing mechanism should be developed. Acknowledgement This work was supported by the Natural Science Foundation of China (60872116, 60773079, 60502039), the HighTech Research and Development Program of China (2007AA01Z477), and the China Postdoctoral post·doc·tor·al also post·doc·tor·ate adj. Of, relating to, or engaged in academic study beyond the level of a doctoral degree. Noun 1. Science Foundation Funded Project (20070420096). Received: September 1, 2008 References [1] H. Wang, and S. Wang, "Cyber Warfare: Steganography vs. Steganalysis," Communication of ACM (Association for Computing Machinery, New York, www.acm.org) A membership organization founded in 1947 dedicated to advancing the arts and sciences of information processing. In addition to awards and publications, ACM also maintains special interest groups (SIGs) in the computer field. , 47(10), pp.7682, 2004. [2] J. Fridrich, and M. Goljan, "Practical Steganalysis of Digital ImagesState of the Art," in Security and Watermarking of Multimedia Contents IV, Proceedings of SPIE SPIE International Society for Optical Engineering SPIE Society of PhotoOptical Instrumentation Engineers SPIE Source Path Isolation Engine SPIE Special Purpose Insertion Extraction SPIE Software Process Improvement Experimentation SPIE Standard Protocols in Effect , 4675, San Jose San Jose, city, United States San Jose (sănəzā`, săn hōzā`), city (1990 pop. 782,248), seat of Santa Clara co., W central Calif.; founded 1777, inc. 1850. , USA, Jan. 2002, pp.113. [3] A. Westfeld, "F5A Steganographic Algorithm," in 4th International Workshop on Information Hiding, Lecture Notes in Computer Science Lecture Notes in Computer Science (LNCS) is a computer science series published by Springer Science+Business Media. , 2137, SpringerVerlag, 2001, pp. 289302. [4] M. Dijk, and F. Willems, "Embedding Information in Grayscale In computing, a grayscale or greyscale digital image is an image in which the value of each pixel is a single sample. Displayed images of this sort are typically composed of shades of gray, varying from black at the weakest intensity to white at the strongest, though in Images," in Proc. 22nd Symp. Inform. Theory in the Benelux, The Netherlands, 2001, pp. 147154. [5] J. Fridrich, and D. Soukal, "Matrix Embedding for Large Payloads," in Security, Steganography, and Watermarking of Multimedia Contents VIII, Proceeding of SPIEIS&T, 6072, 2006, pp. 60721W112. [6] X. Zhang and S. Wang, "Dynamically Running Coding in Digital Steganography," IEEE (Institute of Electrical and Electronics Engineers, New York, www.ieee.org) A membership organization that includes engineers, scientists and students in electronics and allied fields. Signal Processing See DSP. Letters, 13(3), pp. 165168, 2006. [7] X. Zhang and S. Wang, "Efficient Steganographic Embedding by Exploiting Modification Direction," IEEE Communications Letters IEEE Communications Letters is monthly journal published by the IEEE Communications Society. It allows researchers to read about the most current results and developments in communications technology by publishing seven to ten short contributions from every area of communications , 10(11), pp.781783, 2006. [8] J. Fridrich, and P. Lisonek, "Grid Colorings in Steganography," IEEE Trans. Information Theory, 53(4), pp. 15471549, 2007. [9] X. Zhang, W. Zhang and S. Wang, "Efficient DoubleLayered Steganographic Embedding," Electronics Letters Electronics Letters is a journal of the Institution of Engineering and Technology, specializing in short communications on optical electronics. External links
[10] W. Zhang, X. Zhang, and S. Wang, "A Double Layered 'PlusMinus One' Data Embedding Scheme," IEEE Signal Processing Letters, 14(11), pp. 848851, 2007. [11] X. Zhang, W. Zhang, and S. Wang, "Integrated Encoding with High Efficiency for Digital Steganography," Electronics Letters, 43(22), pp. 11911192, 2007. [12] A. Shamir, "How to Share a Secret," Communication of A CM, 22(11), pp.612613, 1979. Xinpeng Zhang, Shuozhong Wang and Weiming Zhang School of Communication and Information Engineering, Shanghai University Shanghai University (University of Shanghai, SHU, 上海大学, 上大) is a public, comprehensive university located in Shanghai, China. Shanghai University is one of the nation's leading research universities in Shanghai, China. , China Email: {xzhang,shuowang,weimingzhang}@shu.edu.cn Table 1. Performance comparison between various steganographic techniques Number PSNR due Steganographic of cover to data Condition for technique images embedding data extraction LSB method 2 52.1 dB All stegoimages Running coding (T= 2) 3 52.9 dB must be received EMD embedding (q = 3) 4 57.8 dB Proposed scheme 53.9 dB Any four (Data decomposition & 6 and stegoimges Stegocoding) 57.8 dB among all the six are received 

Reader Opinion