MultiInfHidingSys.DVI


Mathematical Problems of Computer Science 24, 2005, 89{103.

On I nfor mation H iding System

With M ultiple M essages¤

Ma r ia m E . H a r o u t u n ia n a n d S m b a t A . To n o ya n

Institue for Informatics and Automation Problems of NAS of RA

e-mail armar@ipia.sci.am, smbatt@ipia.sci.am

Abstract

Many algorithms and schemes of multiple watermarking, ¯ngerprinting and multi-
media data creation are implementing to hide more than one watermark. Information
theoretical analysis of information hiding system with multiple messages is considered
in this paper. The rate-reliability-distortion function (which we call the information
hiding E-capacity [5, 9]) for this system, in case of two messages (watermarks) is in-
vestigated. The inner bounds for information hiding E-capacity and for information
hiding capacity [1] regions are constructed.

Refer ences

[1 ] 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 .

[2 ] F. A . P . P e t it c o la s , R . J. A n d e r s o n , a n d M. G. K u h n , " In fo r m a t io n h id in g { A S u r ve y,"
P roc. IE E E (Special Issue on Identi¯cation and P rotection of M ultimedia Information),
vo l. 8 7 , p p . 1 0 6 2 -1 0 7 8 , Ju ly 1 9 9 9 .

[3 ] P . Mo u lin , " Th e r o le o f in fo r m a t io n t h e o r y in wa t e r m a r kin g a n d it s a p p lic a t io n t o
im a g e wa t e r m a r kin g ," Signal P rocessing, vo l. 8 1 , p p . 1 1 2 1 -1 1 3 9 , 2 0 0 1 .

[4 ] 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 ) , 3rd 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 .

[5 ] M. E . H a r o u t u n ia n a n d 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 Intern. Symp. Infrom. Theory, p . 5 3 6 , U S A , Ch ic a g o ,
2 0 0 4 .

[6 ] N . P . S h e p p a r d , R . S a fa vi-N a in i a n d P . Og u n b o n a , " On m u lt ip le wa t e r m a r kin g " , ACM
M ultimedia Conference, ACM M ultimedia, p p 3 -6 , 2 0 0 1 .

[7 ] I. J. Co x, J. K ilia n , T. L e ig h t o n , a n d T. S h a m o o n . " A s e c u r e , r o b u s t wa t e r m a r k
fo r m u lt im e d ia " , Information Hiding: F irst International W orkshop, p p . 1 8 5 -2 0 6 ,
S p r in g e r , B e r lin , Ge r m a n y, 1 9 9 6 .

¤The work was partially supported by 04.10.31 Target Program of RA.

8 9



9 0 On Information Hiding System With Multiple Messages

[8 ] F. Min t z e r a n d G. W . B r a u d a wa y, " If o n e wa t e r m a r k is g o o d , a r e m o r e b e t t e r ?" , IE E E
International Conference on Acoustics, Speech and Signal P rocessing, p p . 2 0 6 7 -2 0 6 9 ,
1 9 9 9 .

[9 ] M. E . H a r o u t u n ia n a n d S . A . To n o ya n , " B o u n d s o f in fo r m a t io n h id in g E-c a p a c it y" ,
S u b m it t e d t o IE E E Trans. Inform. Theory, ( 1 5 p a g e s ) , 2 0 0 4 .

[1 0 ] N . Me r h a v, " On r a n d o m c o d in g e r r o r e xp o n e n t s o f wa t e r m a r kin g s ys t e m s " , IE E E
Trans. Inform. Theory, vo l. 4 6 , n o . 2 , p p . 4 2 0 -4 3 0 , Ma r . 2 0 0 0 .

[1 1 ] N . Me r h a v a n d A . S o m e kh -B a r u c h , " On t h e e r r o r e xp o n e n t a n d c a p a c it y g a m e s o f
p r iva t e wa t e r m a r kin g s ys t e m s " , IE E E Trans. Inform. Theory, vo l. 4 9 , n o . 3 , p p . 5 3 7 -
5 6 2 , Ma r . 2 0 0 3 .

[1 2 ] T. M. Co ve r , " B r o a d c a s t c h a n n e ls " , IE E E Trans. Inform. Theory, vo l. IT-1 8 , n o . 1 ,
p p . 2 { 1 4 , 1 9 7 2 .

[1 3 ] T. M. Co ve r , " A n a c h ie va b le r a t e r e g io n fo r t h e b r o a d c a s t c h a n n e l," IE E E Trans.
Inform. Theory, vo l. IT-2 1 , p p . 3 9 9 { 4 0 4 , 1 9 7 5 .

[1 4 ] M. E . H a r o u t u n ia n , " R a n d o m c o d in g b o u n d fo r E-c a p a c it y r e g io n o f t h e b r o a d c a s t
c h a n n e l" , Tr a n s a c t io n s o f t h e In s t it u t e fo r In fo r m a t ic s a n d A u t o m a t io n P r o b le m s o f
t h e N A S o f R A a n d o f Y S U , M athematical P roblems of Computer Science,vo l. 2 1 , p p .
5 0 { 6 0 , 2 0 0 0 .

[1 5 ] 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 roblems of Control and Information Theory, vo l. 9 , n o . 1 , p p . 1 9 -3 1 , 1 9 8 0 .

[1 6 ] 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 and YSU, M athematical P rob-
lems of Computer sciences, vo l. 2 2 , p . 4 4 -5 9 , 2 0 0 1 .

[1 7 ] M. E . H a r o u t u n ia n , " B o u n d s o f E-c a p a c it y 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 " , s p e c ia l b o o k is s u e d in t h e fr a m e wo r k o f r e s e a r c h p r o je c t " 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 " a t ZiF, B ile fe ld U n ive r s it y, Ge r m a n y,
2 0 0 4 .

[1 8 ] 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 9 ] 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 .

[2 0 ] A . S o m e kh -B a r u c h a n d N . Me r h a v, On t h e r a n d o m c o d in g e r r o r e xp o n e n t s o f t h e
S in g le -U s e r a n d t h e Mu lt ip le -A c c e s s Ge lfa n d -P in s ke r Ch a n n e ls , P roc. of IE E E Intern.
Symp. Infrom. Theory, p . 4 4 8 , U S A , Ch ic a g o , 2 0 0 4 .

´³½Ù³ÏÇ Ñ³Õáñ¹³·ñáõÃÛáõÝÝ»ñáí ïíÛ³ÉÝ»ñ óùóÝáÕ Ñ³Ù³Ï³ñ·Ç Ù³ëÇÝ

Ø. º. гñáõÃÛáõÝÛ³Ý, ê. ². îáÝáÛ³Ý

²Ù÷á÷áõÙ

´³½Ù³ÏÇ çñ³ÝßÙ³Ý, ÇÝãå»ë ݳ¨ ÙáõÉïÇÙ»¹Ç³ÛÇ ëï»ÕÍÙ³Ý ÙÇ ß³ñù ³É·áñÇÃÙÝ»ñ ¨
ë˻ٳݻñ ݳ˳ï»ëáõÙ »Ý óùóÝ»É Ù»ÏÇó ³í»ÉÇ Ñ³Õáñ¹³·ñáõÃÛáõÝÝ»ñ: ²ß˳ï³ÝùáõÙ



M. E. Haroutunian and S. A. Tonoyan 9 1

ϳï³ñí³Í ¿ µ³½Ù³ÏÇ Ñ³Õáñ¹³·ñáõÃÛáõÝÝ»ñáí ïíÛ³ÉÝ»ñ óùóÝáÕ Ñ³Ù³Ï³ñ·»ñÇ
ÇÝýáñÙ³óÇáÝ-ï»ë³Ï³Ý ѻﳽáïáõÃÛáõÝ: ºñÏáõ ѳÕáñ¹³·ñáõÃÛáõÝÝ»ñÇ ¹»åùÇ Ñ³Ù³ñ
Ý»ñÙáõÍí»É ¨ ѻﳽáïí»É ¿ ѳٳϳñ·Ç ³ñ³·áõÃÛáõÝ-Ñáõë³ÉÇáõÃÛáõÝ-ß»ÕáõÙ (E-
áõݳÏáõÃÛáõÝ) ýáõÝÏódzÝ: γéáõóí»É »Ý Ý»ñùÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñ ѳٳϳñ·Ç E-
áõݳÏáõÃÛ³Ý ¨ áõݳÏáõÃÛ³Ý ïÇñáõÛÃÝ»ñÇ Ñ³Ù³ñ: