Matrix_Embedding_for_Large_Payloads.pdf

390

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

VI. C ONCLUSION

Matrix Embedding for Large Payloads

Based on the optimal N–P detector, this letter demonstrates that the

AR watermarking model is as secure as the “white watermark in white

host” model facing the guessing attack (i.e., the spectrum shaping op-

eration does not jeopardize the security of the watermark).

Jessica Fridrich and David Soukal

Abstract— Matrix embedding is a previously introduced coding method

that is used in steganography to improve the embedding efciency (increase

the number of bits embedded per embedding change). Higher embedding

efciency translates into better steganographic security. This gain is more

important for long messages than for shorter ones because longer mes-

sages are, in general, easier to detect. In this paper, we present two new

approaches to matrix embedding for large payloads suitable for practical

steganographic schemes—one based on a family of codes constructed from

simplex codes and the second one based on random linear codes of small

dimension. The embedding efciency of the proposed methods is evaluated

with respect to theoretically achievable bounds.

R EFERENCES

[1] M. Barni and F. Bartolini , Watermarking Systems Engineering: En-

abling Digital Assets Security and Other Applications . New York:

Marcel Dekker, 2004.

[2] M. D. Swanson, B. Zhu, A. H. Tewk, and L. Boney, “Robust audio

watermarking using perceptual masking,” Signal Process. , vol. 66, no.

3, pp. 337–355, 1998.

[3] Q. Cheng and J. Sorensen, “Spread spectrum signaling for speech wa-

termarking,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal

Processing , Salt Lake City, UT, 2001, pp. 1337–1340.

[4] J. K. Su and B. Girod, “Power-spectrum condition for energy-efcient

watermarking,” in Proc. IEEE Int. Conf. Image Processing , Kobe,

Japan, 1999, pp. 301–305.

[5] L. Gang, A. N. Akansu, and M. Ramkumar, “Security and synchro-

nization in watermark sequence,” in Proc. IEEE ICASSP , 2002, vol. 4,

pp. 3736–3739.

[6] S. M. Kay , Fundamentals of Statistical Signal Processing: Detection

Theory . Englewood Cliffs, NJ: Prentice-Hall, 1998.

[7] S. M. Kendall and A. Stuart , The Advanced Theory of Statistics, Volume

1: Distribution Theory . London, U.K.: Grifn, 1977.

[8] S. M. Kay , Fundamentals of Statistical Signal Processing: Estimation

Theory . Englewood Cliffs, NJ: Prentice-Hall, 1993.

[9] C. C. Wai , Speech Coding Algorithms: Foundation and Evolution of

Standardized Coders . New York: Wiley, 2003.

[10] S. M. Ross , Simulation . Singapore: Elsevier, 2006.

Index Terms— Covering codes, embedding efciency, steganography.

I. I NTRODUCTION

The main requirement for a steganographic scheme is statistical un-

detectability. Given the knowledge of the embedding algorithm and the

source of cover media, the attacker should not be able to distinguish be-

tween stego and cover objects with a success rate better than random

guessing. Steganographic security is mostly inuenced by the type of

cover media, the method for selection of places within the cover that

might be modied, the type of embedding operation, and the number of

embedding changes, which is a quantity closely related to the length of

the embedded data. Given two embedding schemes that share the rst

three attributes, the scheme that introduces fewer embedding changes

will be less detectable.

Matrix embedding is a general principle that can be applied to most

steganographic schemes to improve their embedding efciency, which

is dened as the expected number of random message bits embedded

per one embedding change. Matrix embedding was introduced by

Crandall [3], analyzed by Bierbrauer [1], and independently discov-

ered by van Dijk et al. [8] and Galand et al. [5]. It was made popular

by Westfeld who incorporated a specic implementation of matrix

embedding using binary Hamming codes in his F5 algorithm [9]. It is

intuitively clear that the gain in embedding efciency can be larger for

short messages than for longer ones. Since, in general, short messages

are more difcult to detect than longer ones, improving the embedding

efciency for increasingly shorter messages becomes progressively

less important for the overall security. In current steganographic

literature, however, no codes suitable for embedding large payloads

Manuscript received June 20, 2005; revised May 5, 2006. This work was sup-

ported in part by the Air Force Research Laboratory, in part by the Air Force

Material Command, and in part by USAF under Research Grants FA8750-04-1-

0112 and F30602-02-2-0093. The U.S. Government is authorized to reproduce

and distribute reprints for Governmental purposes notwithstanding any copy-

right notation there on. The views and conclusions contained herein are those of

the authors and should not be interpreted as necessarily representing the ofcial

policies, either expressed or implied, of Air Force Research Laboratory or the

U.S. Government. The associate editor coordinating the review of this manu-

script and approving it for publication was Prof. Thomas Johanson.

J. Fridrich is with the Department of Electrical and Computer Engineering,

Binghamton University, State University of New York, Binghamton, NY 13902-

6000 USA.

D. Soukal is with the Department of Computer Science, Binghamton Univer-

sity, State University of New York, Binghamton, NY 13902-6000 USA (e-mail:

dsoukal1@binghamton.edu).

Digital Object Identier 10.1109/TIFS.2006.879281

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

391

were described. The goal of this correspondence is to ll in the gap and

present codes that practitioners will nd useful for implementation.

We describe two approaches. The rst one is based on simplex

codes and codes constructed from them, while the second approach

uses random linear codes of small dimension. In Section II, we intro-

duce the terminology and basic concepts of linear codes necessary to

explain the embedding methods. In Section III, we briey describe the

principles of matrix embedding and state known bounds on achievable

embedding efciency. Matrix embedding based on simplex codes and

random linear codes with small dimension is explained in Section IV.

In the same section, the performance is compared to theoretically

achievable bounds. Pseudocodes are used to describe the embedding

and extraction algorithms to ease the implementation and make this

text self-contained. The correspondence is concluded in Section V.

range [0,255] and n is the number of pixels. Data embedding consists

of modifying the values of selected pixels so that the modied (stego)

image Y conveys the desired secret message. The impact of embedding

is captured by a distortion metric D:G n G n ![0;1) .

In most steganographic schemes, the message (a bit-stream) is com-

municated through a bit-assignment function s:G! 2 that assigns a

bit to each possible pixel value. The most common bit-assignment func-

tion used in steganography is the least-signicant bit (LSB) of pixel

values

s(i)=imod2: (3)

The embedding operation is then designed so that its application to a

pixel value modies its assigned bit. For example, for LSB embedding,

the embedding operation is ipping the LSB of the pixel value. Writing

the pixels of image X as a one-dimensional (1-D) vector, its vector

of bits s(X)=x2 n 2 is obtained by applying s to each element.

Everywhere in this paper, we measure the impact of embedding using

the Hamming distance d: n 2 n 2 !f0;1;...;ng between the

corresponding bit vectors, which is the number of embedding changes

II. N OTATION

Throughout this correspondence, we will use some standard con-

cepts and results from Coding Theory that can be found, for example,

in [10]. Vectors or matrices are in bold and the calligraphic font is

used for sets. Let n 2 denote the space of all n -bit column vectors

x=(x 1 ;...;x n ) t . A binary [n;k] code C of block length n and di-

mension k is a k -dimensional vector subspace of n 2 , where the sum of

two vectors and a multiplication of a vector by scalar are dened using

the usual binary arithmetics. The k basis vectors written as rows of a

matrix form the generator matrix G . The orthogonal complement of

an [n;k] code is an [n;nk] code (called the dual code to C ) with an

(nk)n generator matrix H with the property that Hx=0 for

each x2C . The matrix H is called the parity check matrix of C .

For any x2 n 2 , the vector s=Hx2 nk

D(X;Y)=d(s(X);s(Y)) for all X;Y2G n : (4)

2 is called the syndrome

of x . For each syndrome s2 n 2 , the set C(s)=fx2 n 2 jHx=sg is

called a coset. Note that C(0)=C . Obviously, cosets associated with

different syndromes are disjoint. Also, from elementary linear algebra,

we know that every coset can be written as C(s)=x+C , where

x2C(s) arbitrary. Thus, there are 2 nk disjoint cosets, each con-

sisting of 2 k vectors. Any member of the coset C(s) with the smallest

Hamming weight is called a coset leader and will be denoted as e L (s) .

The Hamming weight w of a vector x is dened as the number of ones

in x (i.e., w(x)=x 1 ++x n ).

The distance between two vectors x and y is dened as the Hamming

weight of their difference d(x;y)=w(xy) . For any x2C ,we

denote as B(x;R) the ball with center x and radius R , B(x;R)=

fy2 n 2 jd(x;y)Rg .

The covering radius R of code C is dened as

We now briey review a few relevant known facts about embedding

schemes and covering codes that appeared in [1] and [5] and establish

some more terminology. Let M be the set of all messages. An embed-

ding scheme on n 2 with a distortion bound R is a pair of embedding

and extraction functions Emb and Ext

Emb: n 2 M! n 2 and Ext: n 2 !M (5)

d(x;Emb(x;m))R for all m2M and x2 n 2

(6)

such that for all m2M and all x2 n 2 , Ext(Emb(x;m))=m .In

other words, (5) means that we can embed any message from M in any

binary n -tuple and (6) states that we can do it using at most R changes.

The value h=log 2 jMj is called the embedding capacity (in bits)

and =h=n the relative payload (in bits per pixel or bpp). We have

the obvious inequality

jMj2 n or 1: (7)

x2 d(x;C) (1)

We further dene e=h=R as the lower embedding efciency and

e=h=R a as the embedding efciency, where R a is the expected

number of changes over uniformly distributed cover objects x2 n 2

and messages m2M . Note that since R is the upper bound on the

number of embedding changes, for any embedding scheme ee . The

reason why we used the same symbols R and R a here that already have

the meaning of the covering radius and average distance to code will

become clear from the matrix embedding theorem below. The matrix

embedding theorem is taken from [1] and [5] and gives a recipe on

how to use an [n;k] code to communicate nk bits using at most R

changes in n pixels.

Theorem 1: ( Matrix embedding ) Let C be an [n;k] code with a parity

check matrix H and covering radius R . The embedding scheme below

can communicate nk bits m2 n 2 in n pixels with bits x using at

most R changes

where d(x;C)=min c2C d(x;c) is the distance between x and

the code C .An R -covering of n 2 is any subset C of n 2 such that

x2C B(x;R)= n 2 , where B(x;R) is the ball with center x and

radius R . The average distance to code is dened as the average

distance between a randomly selected vector from n 2 and the code C

R a = 1

2 n

d(x;C): (2)

Clearly, R a R .

III. M ATRIX E MBEDDING IN S TEGANOGRAPHY

We will assume that the cover image X is an element of G n , where

G is the set of all possible pixel values. For example, in steganography

using 8-bit grayscale digital images, G is the set of all integers in the

Emb(x;m)=x+e L (mHx)=y

Ext(y)=Hy

R=max

392

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

2 is a sequence of nk message bits and e L (mHx)

is a coset leader of the coset C(mHx) .

Indeed, since C has a covering radius R , we know that d(x;y)=

w(e L (mHx))R , which shows that the embedding scheme has

(a tight) distortion bound R . To see that Ext(Emb(x;m))=m ,

note that Ext(Emb(x;m))=Hy=Hx+He L (mHx)=

Hx+mHx=m .

For an embedding scheme realized using matrix embedding, the

expected number of embedding changes for messages uniformly

distributed in nk

payload , or the class of [n;n(1)] codes. An upper bound on e

requires a lower bound on R and R a . Because there are n i possible

sums of i columns of the parity check matrix H , the number of cosets

whose coset leaders have weight i is at most n i . Thus, the covering

radius R must be at least equal to R n for which

0 + n

1 ++ n

R n 1 + n n

R n =2 n

2 is equal to the average weight of all coset leaders

of C . It is reasonable to assume that the messages are drawn uniformly

at random from nk

2 since typically they will be encrypted before

embedding. We now show that the expected number of embedding

changes is equal to the average distance to the code (2). Because any

two words x;y from the same coset C have the same distance from

C:d(x;C)=d(y;C)=w(e L ) , the weight of any coset leader of C ,

we have for the average distance to code

where 0 n <1 is a real number. Besides the lower bound RR n ,

we obtain a lower bound for R a

R a

i=1 i n i +R n n n R

2 n

(11)

and an upper bound

2 n x2

d(x;C)= 1

2 n

d(x;C(s))

e= n

R a n2 n

: (12)

s2 x2C(s)

i=1 i n i +R n n n R

= 1

2 n

2 k w(e L (s))

i=1

IV. M ATRIX E MBEDDING FOR L ARGE P AYLOADS

= 1

2 nk

w(e L (s))

The rst example of matrix embedding given by Crandal [3] and

Westfeld [9] was realized using [2 p 1;2 p 1p;3] Hamming codes.

Here, we can embed p message bits in a block of 2 p 1 pixels by

performing at most one embedding change (we make no change with

probability 2 p ). Thus, the embedding efciency is e p =p=(12 p ) .

Embedding p bits per 2 p 1 pixels means that the relative payload is

=p=(2 p 1) .

Note that Hamming codes do not lead to any embedding efciency

improvement for messages of relative length 2/3 or higher. It is pos-

sible to use Hamming codes for message lengths larger than 2/3 using

a construction called the direct sum [2]. We can divide the message

into two or more segments and embed them in disjoint parts of the

cover using Hamming codes with different parameters. For example,

given a relative payload 0.8 bpp, we may divide it into two halves and

embed the rst half in 0:4n pixels and the second half in 0:6n

pixels. In the rst part, we do not use matrix embedding and embed

with efciency 2, while in the second part, we may use matrix embed-

ding with Hamming codes with p=2 (because we are embedding at

relative message length 0:4=0:6=2=3 ). This will lead to embedding

efciency of 0:8=(0:4=2+0:4=e 2 )=16=7 : =2:286 , which is better

than not using matrix embedding at all but still far from theoretically

achievable e : =0:8=H 1 (0:8)=3:292 .

i=1

2 .

We now state a few useful bounds on the embedding efciency. Be-

cause there are R i=0 n i ways in which one can make R or fewer

changes in n pixels, we have

i =log 2 V(n;R)nH(R=n) (8)

h=log 2 jMjlog 2

i=0

where V(n;R) is the volume of a ball of radius R in n 2 and H(x)=

xlog 2 x(1x)log 2 (1x) , 0x1=2 , is the binary entropy

function. Inequality (8) also gives us an upper bound on the lower em-

bedding efciency e=h=R for a given relative payload =h=n

H 1 () R

n =)e= h

R = n

H 1 () : (9)

We note that this bound is also an asymptotic bound on the embedding

efciency e

A. Matrix Embedding Using Random Linear Codes

Since random linear codes asymptotically achieve the bound (10)

[5], we may attempt to construct good codes randomly. The downside

of random codes is that they lack structure needed for fast encoding.

Fortunately, for large relative payloads with !1 , the codimension

of the code will be close to code length and, thus, the dimension will

be small enough to enable fast nding of coset leaders.

Indeed, to nd the coset leader of the coset C(Hxm) , we can rst

nd an arbitrary vector e satisfying He=Hxm .If c(e) is the

closest codeword to e , then ec(e) is the coset leader of C(Hxm)

because

H 1 ()

(10)

which holds for almost all [n;n(1)] codes because the relative

covering radius =R=n and the relative distance to code a =R a =n

converge with n!1 . To state this more precisely, we formulate (and

prove in the Appendix) the following theorem.

Theorem 2: For any 0<<1 and any >0 , the fraction of

all binary [n;(1)n] codes for which j a j tends to 1 as

n!1 .

We close this section with one more useful bound on the embedding

efciency for codes restricted to a class of linear codes with relative

d(e;c(e))=min

c2C(Hxm) w(ec)=w(e L (Hxm)):

where m2 nk

which is the average number of embedding changes for messages uni-

formly chosen from nk

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

393

We note that if H is generated randomly but already in a systematic

form, 1 nding e will be trivial. Thus, the most time consuming part

of encoding is determining the closest codeword c(e) . Since there are

2 k codewords, keeping the table of all codewords in memory requires

n2 k bits. Finding the closest codeword requires the same order of com-

putations O(n2 k ) . To keep the complexity and memory requirements

low, the code dimension k should be small (e.g., k14 ). We note

that for a xed k , the relative payload n for the class of [n;k] codes

is n =(nk)=n . The pseudocode for embedding is given in Algo-

rithm 1.

Algorithm 1 Embedding M bits in an N -element cover object using

random linear codes.

1 .

2) Read the next n bits x from the cover object (along a stego-key

dependent path) and the next message segment m of length

nk .

3) Find any e that solves He=mHx .

4) In the list of all 2 k codewords, nd the closest codeword to e ,

denote c(e) .

5) [Embedding modications] y=x+ec(e) is the stego object.

6) If we are at the end of the cover object, stop; otherwise, go to 1.

7) [Extraction step] The message bits are extracted by following the

same embedding path and calculating nk bits m from each

block y of the stego object m=Hy .

Fig. 1. Embedding efciency versus relative capacity (large payload case).

TABLE I

S PEED OF E MBEDDING FOR 1.3 M EGA -P IXEL I MAGE

W ITH F IXED B LOCK L ENGTH n=100

While the parameter k can be public knowledge, the block length

n must be communicated to the recipient in the stego image itself be-

cause it depends on the message length. This is also the only piece of

information that needs to be communicated along with the payload. 2

One possibility is to encode n using regular (nonmatrix) embedding in

a small subset of pixels pseudorandomly chosen using the shared secret

stego-key. The same stego-key can be used to generate the (nk)n

matrix H using a pseudorandom number generator so that it does not

have to be communicated. Alternatively, the matrix H could be even

public as long as the message bits are embedded along a pseudorandom

path generated from the stego-key.

Fig. 1 shows the embedding efciency of random linear codes for

k=10 and k=14 for n165 . A nice feature of random codes

is that they provide an almost continuously changing family of codes

with the same coding algorithm, allowing the sender to choose the code

length n to match n =(nk)=n to the relative payload length and,

thus, use the whole embedding space in the cover object.

To see how much the coding improves the embedding efciency, let

us take two relative payloads 0.9 and 0.8. From Fig. 1, using random

linear codes of dimension 14, the embedding efciency improves from

2 (no coding) to approximately 2.7 and 3, respectively. Thus, the coding

reduces the impact of embedding the two messages as if we were em-

bedding messages of length (0:92)=2:7 : =0:67 and (0:82)=3 : =

0:53 , respectively, without any coding. This is a signicant improve-

ment in view of the fact that the performance of current steganalyzers

for some embedding methods may be quite sensitive to the relative pay-

load in this range (see, for example, [6] and [7]).

Note that the embedding efciency of random codes is fairly

close to the upper bound (11) for codes of the same length. The

strange little “wiggles” in the upper bound are not a computing

artifact but a real phenomenon whose explanation can be found

in [4].

We can also see in Fig. 1 that the increase in embedding efciency

as the code dimension is increased from 10 to 14. Better performance

could be obtained by further increasing the code dimension at the price

of exponentially increasing complexity. Even though typical stegano-

graphic algorithms are run ofine on a computer and, thus, have less

stringent requirements on complexity than typical channel coding ap-

plications, the code dimension cannot be increased much without a

severe complexity increase (recall that the complexity of coding is

O(n2 n(1

B. Matrix Embedding Using Simplex Codes

Any structured codes with low dimension and fast decoding algo-

rithms that are quantizers can be used for our purpose. In this section,

we study the performance of the dual to Hamming codes—the simplex

codes.

In Algorithm 2, we give the pseudocode for matrix embedding using

the simplex codes. The decoding algorithm for simplex codes can be

found, for example, in [10]. We note that H is a parity check matrix of

the [2 q 1;q] simplex code, H 2 is the Hadamard (Sylvester) matrix

of order 2 q , and the symbol 1 is a column vector of 2 q ones.

1 H=[I ;D] , where I is a square (nk)(nk) identity matrix.

2 If we limit ourselves, for example, to n 256, we would only need 8 bits

for this overhead.

1) To embed M bits in an N -element cover object, rst nd n such

that n (M=N)> n

) ) .

In Table I, we give a small example of how fast the embedding based

on random codes runs on a computer. We simulated embedding into an

image with N=12801024 pixels using a random code with block

length n=100 . We measured the time taken to perform the embedding

with dimensions k=10 , 12, and 14. The test was performed on a

Pentium IV running at 3.4 GHz with 1-GB random-access memory

(RAM). The algorithm was implemented in C++ and compiled under

Linux with GCC 3.4.3.

394

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006

Algorithm 2 Embedding M bits in an N -element cover object using

simplex codes.

We showed that random linear codes provide good embedding ef-

ciency and their relative embedding capacity densely covers the range

of large payloads, making such codes suitable for practical applica-

tions. Matrix embedding using simplex codes is more computationally

efcient and can be used even for relative payloads above 0.9.

In this paper, we also introduce a new concept of an average dis-

tance to code as it is more relevant and directly related to embedding

efciency as currently used in steganography. We derive asymptotic

bounds on the average distance to code to better contrast the perfor-

mance of the proposed codes to the theoretically achievable embedding

efciency. The average distance to code asymptotically coincides with

the covering radius with increasing code length. However, for small

code lengths, codes with the smallest average distance to code may not

necessarily have the smallest covering radius. We plan to elaborate on

this issue in our future work.

1 1) .

2) Read the next p=2 q 1 bits x from the cover object and the

next message segment m of length p=2 q 1q (follow a

pseudorandom path through the image).

3) Find any e that solves He=mHx (e.g., using Gaussian

elimination).

4) For ^e=(0;e 1 ;...;e 2

1 q)=(2 q

1 ) , calculate E=(12^e)H 2 using

the fast Hadamard transform.

5) E i =maxfE 1 ;...;E 2 g , u = binary expansion of i 0 1

(LSB is the last).

6) The closest codeword to e is c(e)= q i=1 u i v t i , where v i is the

i th row of the generator matrix G .

7) [Embedding modications] y=x+ec(e) is the stego object.

8) If we are at the end of the cover object, stop; otherwise, go to 1.

A PPENDIX

Before we give a proof of Theorem 2, we formulate two auxiliary

lemmas.

Lemma 1: For any 0<1=2 , there exists an integer sequence

k n with

Other codes derived from simplex codes using common operations

on codes, such as lengthening (increasing length by one) or augmenting

(adding a codeword to the generator matrix), also give good perfor-

mance and can be decoded using a simple modication of the decoding

algorithm for simplex codes. If we augment the simplex code with an

all-one vector (1;...;1) , we obtain a [2 q 1;q+1] code, which co-

incides with the punctured rst-order Reed–Muller code [10].

To embed with this code, we need to slightly modify Algorithm

2. We need to run Step 4 with e prepended with both “0” and “1”:

^e 0 =(0;e 1 ;...;e 2

k n =n1H()+f(n)

1 logn) , such that the fraction of all binary [n;k n ]

codes that are bnc -coverings tends to 1.

Proof: This lemma is proved in [2, p. 325] (Theorem 12.3.5).

Lemma 2: For any H

1 ()<<1=2 , the fraction of all binary

[n;(1)n] codes with covering radius at most bnc tends to 1 as

n!1 .

Proof: Let us denote ? =H

1 ) , obtaining now

two vectors c 0 and c 1 in Step 6, taking the vector closer to e as c(e) .

To avoid calculating the Hadamard transform twice, note that (1

2^e 1 )H 2 =(12^e 0 )H 2 2h 1 , where h 1 is the rst row of H 2 .

The embedding efciency of simplex codes and augmented simplex

codes for q=3;...;11 is shown in Fig. 1. Note that their performance

is not as good as that of random linear codes. Also, they do not cover

the range of as densely as random codes—their relative payloads are

q =(2 q 1q)=(2 q 1) and q =(2 q 2q)=(2 q 1) for

the simplex and augmented simplex codes, respectively. On the other

hand, they easily reach into the range of relative payload close to 1 and

they do so with low computational complexity O(q2 q )=O(nlogn)

in terms of the code length n .

Again, to give an example of the improvement obtained from embed-

ding using these structured codes for a relative payload 0.94, the appli-

cation of the augmented simplex code leaves the same impact as an

uncoded embedding of a message with relative length (0:92)=2:4=

0:75 , which is an improvement of about 20%.

We note that the parameter q is again the only information that needs

to be communicated to the recipient in the same manner as described

in the previous section.

1 ) and ^e 1 =(1;e 1 ;...;e 2

1 () . Because 1H()<1

H( ? ) and f(n)!0 as n goes to innity, there exists n 0 such that

for any n>n 0

1H()+f(n)1H( ? )=1:

Applying Lemma 1 to , we obtain an integer sequence k n for which

k n =n1H()+f(n)1H( ? )=1

for n>n 0 . Thus, k n (1)n and the fraction of all [n;k n ]

codes whose covering radius is at most bnc tends to one. However,

the same is true for at least the same fraction of [n;(1)n] codes as

well. This is so because for any two codes C 1 C 2 , C 1 an [n;k 1 ] code

with covering radius R 1 and C 2 an [n;k 2 ] code with covering radius

R 2 ,wehave R 2 R 1 .

Proof of Theorem 2: Let ? =H

1 ()R=n= . On the other

hand, from Lemma 2, it follows that ? + for all n>n 0 , for a

fraction of all [n;(1)n] codes that goes to 1 as n!1 .

The average distance to such codes is R a =(1=2 n ) n

V. C ONCLUSION

l=0 lc l ,

where c l is the number of coset leaders of weight l . Because a ,

we need a lower bound on a . Writing

In this paper, we present two simple coding schemes suitable for ma-

trix embedding of large payloads. The codes can be applied to most

steganographic schemes without any other changes to their embed-

ding mechanism to increase their embedding efciency—the expected

number of random bits embedded using one embedding change. This

will improve their steganographic security.

R a = 1

2 n

b (

)n c

lc l + 1

2 n

lc l (13)

l=0

l=b()nc+1

1) To embed M bits in an N -element cover object, rst nd q such

that (2 q 1q)=(2 q 1)(M=N)>(2 q

where f(n)2O(n

1 () and let C be an [n;(1

)n] code. From (8) applied to C (note that h=n ), we have for its

relative covering radius , ? =H

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: