D:\sbornik\...\rev.DVI


Mathematical Problems of Computer Science 28, 2007, 18{33.

Random Coding B ound of Rever sible I nfor mation

H iding E-capacity¤

Ma r ia m H a r o u t u n ia n y, S m b a t To n o ya n y, Ole ks iy K o va lz, S vya t o s la v V o lo s h yn o vs kiyz

y Institue for Informatics and Automation Problems of NAS of RA
e-mail: farmar, smbattg@ipia.sci.am
zUniversity of Geneva, Switzerland

e-mail: fOleksiy.Koval, svolosg@cui.unige.ch

Abstract

In this paper we consider the problem of reversible information hiding in the case
when the attacker uses only discrete memoryless channels (DMC), the decoder knows
only the class of channels, but not the DMC chosen by the attacker, the attacker knows
the information-hiding strategy, probability distributions of all random variables, but
not the side information.

We introduce the notion of reversible information hiding E-capacity, which ex-
presses the dependence of the information hiding rate on the error probability exponent
and the distortion levels for information hider, for attacker and for the host data ap-
proximation. The random coding bound for reversible information hiding E-capacity
is found. When E ! 0 we obtain the lower bound for reversibility information hiding
capacity.

In particular, we have analyzed two special cases of the general problem formulation,
pure reversibility and pure message communications.

Refer ences

[1 ] A . V . K u s n e t s o v a n d B . S . Ts yb a ko v, " Co d in g in a m e m o r y wit h d e fe c t ive c e lls " , ( in
R u s s ia n ) , P robl. P eredachi Informacii, vo l. 1 0 , n u m . 2 , p . 5 2 -6 0 , 1 9 7 4 .

[2 ] S . I. Ge l'fa n d a n d M.S . P in s ke r , " Co d in g fo r c h a n n e l wit h r a n d o m p a r a m e t e r s " , P robl.
Control and Inf. Theory, vo l. 9 , n u m . 1 , p . 1 9 -3 1 , 1 9 8 0 .

[3 ] M. Co s t a , " W r it in g o n d ir t y p a p e r " , IE E E Trans. on Information Theory, vo l. 2 9 ,
n u m . 3 , p . 4 3 9 -4 4 1 , 1 9 8 3 .

[4 ] H . C. P a p a d o p o u lo s a n d C.-E . W . S u n d b e r g , " S im u lt a n e o u s b r o a d c a s t in g o f a n a lo g
FM a n d d ig it a l a u d io s ig n a ls b y m e a n s o f a d a p t ive p r e c a n c e lin g t e c h n iqu e s " , IE E E
Trans. on Communicationsy, vo l. 4 6 , n u m . 9 , p . 1 2 3 3 -1 2 4 2 , 1 9 9 8 .

¤The work was partially supported by the CRDF and NFSAT grant GRSP 09/06.

1 8



M. Haroutunian, S. Tonoyan, O. Koval, S. Voloshynovskiy 1 9

[5 ] F. M. J. W ille m s a n d T. K a lke r , " Me t h o d s fo r r e ve r s ib le e m b e d d in g ," P roc. 40th
Annual Allerton Conference on Communication, Control, and Computing, A lle r t o n
H o u s e , Mo n t ic e llo , Illin o is , Oc t . 2 -4 , 2 0 0 2 .

[6 ] T. K a lke r a n d F. M. W ille m s , " Co d in g Th e o r e m s fo r R e ve r s ib le E m b e d d in g ," D IM ACS
W orkshop on Network Information Theory, R u t g e r s U n ive r s it y, P is c a t a wa y, N J, vo l.
6 6 , Ma r c h 2 0 0 3 .

[7 ] E . Ma r t in ia n , G. W . W o r n e ll a n d B . Ch e n , " A u t h e n t ic a t io n wit h D is t o r t io n Cr it e r ia " ,
IE E E Trans. on Information Theory, vo l. 5 1 , n u m . 7 , p . 2 5 2 3 -2 5 4 2 , 2 0 0 5 .

[8 ] S . V o lo s h yn o vs kiy, O. K o va l, E . To p a k, J. V ila a n d T. P u n , " P a r t ia lly r e ve r s ib le d a t a
h id in g wit h p u r e m e s s a g e c o m m u n ic a t io n s " , IE E E Trans. on Information F orensics
and Security, s u b m it t e d fo r p u b lic a t io n s .

[9 ] A . S u t ivo n g , M. Ch ia n g , T.M. Co ve r a n d Y .-H . K im , " Ch a n n e l Ca p a c it y a n d S t a t e
E s t im a t io n fo r S t a t e -D e p e n d e n t Ga u s s ia n Ch a n n e ls " , IE E E Trans. on Information
Theory, vo l. 5 1 , n u m . 4 , p . 1 4 8 6 -1 4 9 5 , 2 0 0 5 .

[1 0 ] E . A . H a r o u t u n ia n , " U p p e r e s t im a t e o f t r a n s m is s io n r a t e fo r m e m o r yle s s c h a n n e l wit h
c o u n t a b le n u m b e r o f o u t p u t s ig n a ls u n d e r g ive n e r r o r p r o b a b ilit y e xp o n e n t " ( in R u s -
s ia n ) , III All-Union Conf. on Theory of Information Transmission and Coding, Uzh-
gorod, P ublication House of Uzbek Academy of Sciences, Tashkent, p p . 8 3 -8 6 , 1 9 6 7 .

[1 1 ] M. E . H a r o u t u n ia n , S . A . To n o ya n , " R a n d o m c o d in g b o u n d o f in fo r m a t io n h id in g
E -c a p a c it y" , P roc. of IE E E International Symposium on Information Theory, p . 5 3 6 ,
U S A , Ch ic a g o , 2 0 0 4 .

[1 2 ] M. E . H a r o u t u n ia n a n d S . A . To n o ya n , " On e s t im a t e s o f r a t e -r e lia b ilit y-d is t o r t io n
fu n c t io n fo r in fo r m a t io n h id in g s ys t e m " , Transactions of the Institute for Informatics
and Automation P roblems of the NAS of R A. M athematical P roblems of Computer
Scence 23, p p . 2 0 -3 1 , 2 0 0 4 .

[1 3 ] M. E . H a r o u t u n ia n , " N e w b o u n d s fo r E-c a p a c it ie s o f a r b it r a r ily va r yin g c h a n n e l a n d
c h a n n e l wit h r a n d o m p a r a m e t e r " , Trans. IIAP NAS R A, M athematical P roblems of
Computer sciences, vo l. 2 2 , p . 4 4 -5 9 , 2 0 0 1 . A va ila b le a t h t t p :/ / ip ia .s c i.a m / it a s .

[1 4 ] M. E . H a r o u t u n ia n , " E s t im a t e s o f E-c a p a c it y a n d c a p a c it y r e g io n s fo r m u lt ip le -a c c e s s
c h a n n e l wit h r a n d o m p a r a m e t e r " , E lectronic Notes in D iscrete M athematics, v.2 1 ,
Ge n e r a l Th e o r y o f In fo r m a t io n Tr a n s fe r a n d Co m b in a t o r ic s , p p . 3 0 3 -3 0 8 , 2 0 0 5 . A va il-
a b le a t h t t p :/ / www.s c ie n c e d ir e c t .c o m / s c ie n c e .

[1 5 ] I. Cs is z ¶a r a n d J. K Äo r n e r , Information Theory: Coding theorems for discrete memoryless
systems, A c a d e m ic P r e s s , N e w Y o r k, 1 9 8 1 .

[1 6 ] I. Cs is z ¶a r , " Th e m e t h o d o f t yp e s " , IE E E Trans. Inform. Theory, vo l. 4 4 , n o . 6 , p p .
2 5 0 5 { 2 5 2 3 , 1 9 9 8 .

[1 7 ] P . Mo u lin a n d J. A . O'S u lliva n , " In fo r m a t io n -t h e o r e t ic a n a lys is o f in fo r m a t io n h id in g " ,
IE E E Trans. Inform. Theory, vo l. 4 9 , n o . 3 , p p . 5 6 3 -5 9 3 , Ma r . 2 0 0 3 .

[1 8 ] T. M. Co ve r a n d J. A . Th o m a s , E lements of Information Theory, W ile y, N e w Y o r k,
1 9 9 1 .

[1 9 ] E . A . H a r o u t u n ia n a n d H . B e lb a s h ir , " L o we r b o u n d o f t h e o p t im a l t r a n s m is s io n r a t e
d e p e n d in g o n g ive n e r r o r p r o b a b ilit y e xp o n e n t fo r d is c r e t m e m o r yle s s c h a n n e l a n d fo r



2 0 Random Coding Bound of Reversible Information Hiding E-capacity

a s ym m e t r ic b r o a d c a s t c h a n n e l" , ( in R u s s ia n ) , Abstracts of papers of Sixth International
Symposium on Information Theory, Tashkent, USSR , vo l. 1 , p p . 1 9 -2 1 , 1 9 8 4 .

î»Õ»ÏáõÃÛáõÝÝ»ñ óùóÝáÕ ßñç»ÉÇ Ñ³Ù³Ï³ñ·Ç E-áõݳÏáõÃÛ³Ý
å³ï³Ñ³Ï³Ý Ïá¹³íáñÙ³Ý ·Ý³Ñ³ï³Ï³ÝÁ

Ø. гñáõÃÛáõÝÛ³Ý, ê. îáÝáÛ³Ý, ú. Îáí³É, ê. ìáÉáßÇÝáíëÏÇ

²Ù÷á÷áõÙ

²ß˳ï³Ýùáõ٠ѻﳽáïí³Í ¿ ï»Õ»ÏáõÃÛáõÝÝ»ñÇ ßñç»ÉÇ Ã³ùóÙ³Ý ÇÝýáñÙ³óÇáÝ-
ï»ë³Ï³Ý ËݹÇñÁ: ¸Çï³ñÏí³Í ѳٳϳñ·Ç ѳٳñ ѻﳽáïí»É ¿ E-áõݳÏáõÃÛáõÝ
ýáõÝÏódzÝ: ²ÛÝ Çñ»ÝÇó Ý»ñϳ۳óÝáõÙ ¿ ï»Õ»ÏáõÃÛáõÝÝ»ñÇ Ã³ùóÙ³Ý ³ñ³·áõÃÛ³Ý
ϳËí³ÍáõÃÛáõÝÁ Ñáõë³ÉÇáõÃÛáõÝÇó, ï»Õ»ÏáõÃÛáõÝÝ»ñ óùóÝáÕÇ áõ ѳñÓ³ÏíáÕÇ Ñ³Ù³ñ
ÃáõÛɳïñ»ÉÇ ß»ÕÙ³Ý Ù³Ï³ñ¹³ÏÝ»ñÇó ¨ Ý³ËÝ³Ï³Ý ïíÛ³ÉÝ»ñÇ í»ñ³Ï³Ý·ÝÙ³Ý Ñ³Ù³ñ
ÃáõÛɳïñ»ÉÇ ß»ÕÙ³Ý Ù³Ï³ñ¹³ÏÇó: E-áõݳÏáõÃÛ³Ý Ñ³Ù³ñ ϳéáõóí»É ¿ å³ï³Ñ³Ï³Ý
Ïá¹³íáñÙ³Ý ·Ý³Ñ³ï³Ï³Ý: гٳå³ï³ëË³Ý ·Ý³Ñ³ï³Ï³Ý ¿ ëï³óí»É ѳٳϳñ·Ç
áõݳÏáõÃÛ³Ý Ñ³Ù³ñ:

àõëáõÙݳëÇñí»É »Ý ݳ¨ »ñÏáõ Ù³ëݳíáñ ¹»åù»ñª Ù³ùáõñ ßñç»ÉÇáõÃÛ³Ý ¨
ѳÕáñ¹³·ñáõÃÛáõÝÝ»ñÇ Ù³ùáõñ ѳÕáñ¹Ù³Ý ¹»åù»ñÁ: