D:\User\sbornik_38_pdf\15.DVI


Mathematical Problems of Computer Science 38, 34{36, 2012.

On Random Coding B ound for E-capacity Region of

the B r oadcast Channel With Con¯dential M essages

N a s r in A fs h a r , E vg u e n i H a r o u t u n ia n a n d Ma r ia m H a r o u t u n ia n

Institute for Informatics and Automation Problems of NAS of RA

Th e in fo r m a t io n t h e o r e t ic s e c u r it y r e c e n t ly h a s a t t r a c t e d m u c h a t t e n t io n [8 ]. On e o f t h e
im p o r t a n t o b je c t s in t h e s e c u r e c o m m u n ic a t io n is t h e b r o a d c a s t c h a n n e l wit h c o n ¯ d e n t ia l
m e s s a g e s ( B CC) ¯ r s t in ve s t ig a t e d b y Cs is z ¶a r a n d K Äo r n e r [1 ]. Th e m o d e l is d e p ic t e d in Fig .1 .
Th e B CC in vo lve s t wo d is c r e t e m e m o r yle s s c h a n n e ls wit h t wo s o u r c e s , o n e e n c o d e r a n d t wo
r e c e ive r s . A c o m m o n m e s s a g e m u s t b e t r a n s m it t e d a t r a t e R0 t o b o t h r e c e ive r s a n d a p r iva t e
m e s s a g e t o t h e in t e n d e d r e c e ive r a t r a t e R1 wh ile ke e p in g t h e o t h e r r e c e ive r ig n o r a n t o f it
wit h e qu ivo c a t io n r a t e Re.

@
@

@R

¡
¡

¡µ
-

-

-

- -

- -

- -

Source

Source

M

L

m

l

Encoder
f

x

Channel

WY jX

y Decoder
g1

m0; l0
Receiver 1

m00Channel
WZjX

l00

z Decoder
g2

Receiver 2

Decoder
g02

Figure 1. The discrete memoryless broadcast channel with con¯dential messages.

Th e E-c a p a c it y is a n im p o r t a n t c o n c e p t in in fo r m a t io n t h e o r y [6 ]. Th e E-c a p a c it y ( r a t e -
r e lia b ilit y fu n c t io n ) fo r a d is c r e t e m e m o r yle s s c h a n n e l ( D MC) wa s in t r o d u c e d b y E . H a r o u t u -
n ia n in 1 9 6 7 [3 ]. It p r e s e n t s d e p e n d e n c e b e t we e n r a t e R a n d r e lia b ilit y E ( e r r o r p r o b a b ilit y
e xp o n e n t ) o f o p t im a l c o d e s . Th e fu n c t io n d e n o t e d b y R ( E ) ( a n d a ls o C ( E ) ) [3 ] , [4 ] is
in ve r s e t o t h e S h a n n o n 's r e lia b ilit y fu n c t io n E ( R) . Fu r t h e r m o r e , t h e c o n c e p t o f E-c a p a c it y
c a n b e c o n s id e r e d a s a g e n e r a liz a t io n o f t h e S h a n n o n 's c h a n n e l c a p a c it y. W h e n E g o e s t o
z e r o , t h e fu n c t io n C ( E ) t e n d s t o t h e c h a n n e l c a p a c it y C, a n d wh e n E g o e s t o in ¯ n it y, t h e
C ( E ) g o e s t o z e r o -e r r o r c a p a c it y C0.

Cs is z ¶a r a n d K Äo r n e r fo u n d t h e c a p a c it y r e g io n o f t h e B CC [1 ]. L iu e t a ll p r o p o s e d t h e
c a p a c it y r e g io n o f t h e B CC wit h t wo c o n ¯ d e n t ia l m e s s a g e s [9 ]. X u , Ca o a n d Ch e n in ve s t i-
g a t e d a n in n e r b o u n d o n t h e c a p a c it y r e g io n o f t h e B CC wit h o n e c o m m o n m e s s a g e a n d t wo
c o n ¯ d e n t ia l m e s s a g e s ( B C-2 CM) [1 1 ]. R a n d o m c o d in g b o u n d a n d s p h e r e p a c kin g b o u n d fo r
E-c a p a c it y o f D MC a r e s t u d ie d in [5 ], [6 ]. R a n d o m c o d in g b o u n d fo r t h e 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 wit h o n e c o m m o n m e s s a g e a n d t wo p r iva t e m e s s a g e s wa s fo u n d in
[7 ].

3 4



N. Afshar, E. Haroutunian and M. Haroutunian 3 5

In t h is p a p e r , we in ve s t ig a t e t h e B CC. W e c o n s id e r e r r o r p r o b a b ilit y e xp o n e n t s ( r e lia -
b ilit ie s ) : E1; E2; E3; o f e xp o n e n t ia lly d e c r e a s e o f e r r o r p r o b a b ilit y o f, r e s p e c t ive ly, t h e ¯ r s t
d e c o d e r , t h e s e c o n d d e c o d e r a n d o f t h e d e c o d e r t r yin g t o ¯ n d t h e c o n ¯ d e n t ia l m e s s a g e . Fo r
E = ( E1; E2; E3 ) t h e E-c a p a c it y r e g io n is t h e s e t o f a ll a c h ie va b le r a t e t r ip le s R0; R1; Re
o f c o d e s wit h g ive n r e lia b ilit ie s E1; E2; E3. W e c o n s t r u c t a 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 CC. W h e n e r r o r p r o b a b ilit y e xp o n e n t s a r e g o in g t o z e r o , t h e lim it o f
t h is b o u n d c o in c id e s wit h t h e c a p a c it y r e g io n o f t h e B CC o b t a in e d b y Cs is z ¶a r a n d K Äo r n e r .
Th e n o t io n o f E-c a p a c it y r e g io n is u s e d a ls o fo r e s t im a t io n o f e qu ivo c a t io n r a t e .

It s h o u ld b e n o t e d , t h a t t h e c o n s id e r a t io n o f t h e E-c a p a c it y u p p e r b o u n d o f s e c r e c y
le a ka g e , wh ic h is t h e r a t e o f a va ila b le in fo r m a t io n o f u n in t e n d e d r e c e ive r wit h r e s p e c t t o t h e
p r iva t e m e s s a g e , is a n o n -s t a n d a r d a p p r o a c h t o lo we r b o u n d c o n s t r u c t io n o f e qu ivo c a t io n
r a t e in t h e B CC.

R e s u lt Fo r m u la t io n . Co n s id e r R V s X; Y; Z a n d a u xilia r y R V s U0; U1 wit h jo in t
P D s :

Q ± P1 ± VY jX = fQ ± P1 ± VY jX ( u0; u1; x; y ) = Q0 ( u0 ) Q1j0 ( u1ju0 ) P1 ( xju1 ) VY jX ( yjx ) g; ( 1 )
Q ± P1 ± VZjX = fQ ± P1 ± VZjX ( u0; u1; x; z ) = Q0 ( u0 ) Q1j0 ( u1ju0 ) P1 ( xju1 ) VZjX ( zjx) g: ( 2 )
W e d e ¯ n e t h e fo llo win g fu n c t io n s a p p e a r in g in o u r in n e r e s t im a t e s o f E-c a p a c it y r e g io n :

R¤0 ( Q; P1; E1; E2 )
4
=

m in
½

m in
VY jX :D(VY jX kWY jX jQ1;P1)·E1

¯̄
¯̄IQ;P1;VY jX ( U0 ^ Y ) + D ( VY jXkWY jXjQ1; P1 ) ¡ E1

¯̄
¯̄
+

;

m in
VZjX :D(VZjX kWZjX jQ1;P1)·E2

¯̄
¯̄IQ;P1;VZjX ( U0 ^ Z ) + D ( VZjXkWZjXjQ1; P1 ) ¡ E2

¯̄
¯̄
+¾

; ( 3 )

R¤1 ( Q; P1; E1 )
4
=

m in
VY jX :D(VY jX kWY jX jQ1;P1)·E1

¯̄
¯̄IQ;P1;VY jX ( U1 ^ Y jU0 ) + D ( VY jXkWY jXjQ1; P1 ) ¡ E1

¯̄
¯̄
+

; ( 4 )

R¤e ( Q; P1; E1; E3 )
4
=

m in
VY jX :D(VY jX kWY jX jQ1;P1)·E1

¯̄
¯̄IQ;P1;VY jX ( U1 ^ Y jU0 ) + D ( VY jXkWY jXjQ1; P1 ) ¡ E1

¯̄
¯̄
+

¡

m in
VZjX :D(VZjX kWZjXjQ1;P1)·E3

IQ;P1;VZjX ( U1 ^ ZjU0 ) : ( 5 )

L e t u s c o n s id e r t h e fo llo win g b o u n d s o f r a t e s R0; R1; Re:

0 · R0 + R1 · R¤0 ( Q; P1; E1; E2 ) + R¤1 ( Q; P1; E1 ) ; ( 6 )
0 · R0 · R¤0 ( Q; P1; E1; E2 ) ; ( 7 )

0 · Re · R¤e ( Q; P1; E1; E3 ) ; Re · R1: ( 8 )
Th e r e s u lt o f t h e p a p e r is fo r m u la t e d in t h e fo llo win g

THEOREM 1 . F or E1 > 0 ; E2 > 0 ; E3 > 0 , the region

R¤ ( E ) 4=
[

Q;P1

f( R0; R1; Re ) : ( 6 ¡ 8 ) take place for U0 ! U1 ! X ! ( Y; Z ) g ( 9 )

is an inner bound for E-capacity region C ( E ) of the B CC:
R¤ ( E ) µ C ( E ) µ C ( E ) :



3 6 On Random Coding Bound for E-capacity Region of the Broadcast Channel With Con¯dential Messages

Refer ences

[1 ] I. Cs is z ¶a r a n d J. K Äo r n e r , \ B r o a d c a s t c h a n n e l wit h c o n ¯ d e n t ia l m e s s a g e s " , IE E E Trans.
Inf. Theory, vo l. IT-2 4 , n o . 3 , p p . 3 3 9 -3 4 8 , 1 9 7 8 .

[2 ] I. Cs is z ¶a r a n d J. K Äo r n e r , \ Information Theory: Coding Theorems for D iscrete M emo-
ryless Systems" , N e w Y o r k, W ile y, 1 9 8 1 .

[3 ] 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 " , 3rd All
Union Conference on Theory of Information Transmission and Coding, Uzhgorod, P ub-
lishing House of the Uzbek Academy of Sciences, p p . 8 3 -8 6 , 1 9 6 7 .

[4 ] E . A . H a r o u t u n ia n , B . 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 e m e m o r yle s s c h a n n e l a n d fo r
a s ym m e t r ic b r o a d c a s t c h a n n e l" , Abstracts of P apers of 6th Int. Symp. Inf. Theory,
Tashkent, USSR , vo l. 1 , p p . 1 9 -2 1 , 1 9 8 4 .

[5 ] E . A . H a r o u t u n ia n , \ On B o u n d s fo r E -Ca p a c it y o f D MC" , IE E E Trans. Inf. Theory,
vo l. IT-5 3 , n o . 1 1 , p p . 4 2 1 0 -4 2 2 0 , 2 0 0 7 .

[6 ] E . A . H a r o u t u n ia n , M. E . H a r o u t u n ia n a n d A . N . H a r u t yu n ya n , \ R e lia b ilit y c r it e r ia
in in fo r m a t io n t h e o r y a n d in s t a t is t ic a l h yp o t h e s is t e s t in g " , F oundations and Trends in
Communications and Information Theory, vo l. 4 , n o s . 2 -3 , 2 0 0 8 .

[7 ] 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" , M athematical P roblems of Computer Science, n o . 2 1 , p p . 5 0 -6 0 , 2 0 0 0 .

[8 ] Y . L ia n g , H . V . P o o r a n d S . S h a m a i, \ In fo r m a t io n t h e o r e t ic s e c u r it y" , F oundations and
Trends in Communications and Information Theory, vo l. 5 , n o s . 4 -5 , 2 0 0 9 .

[9 ] R . L iu , I. Ma r ic , P . S p a s o je vic a n d R . Y a t e s , \ D is c r e t e m e m o r yle s s in t e r fe r e n c e a n d
b r o a d c a s t c h a n n e ls wit h c o n ¯ d e n t ia l m e s s a g e s : s e c r e c y r a t e r e g io n s " , IE E E Trans. Inf.
Theory, vo l. 5 4 , n o . 6 , p p . 2 4 9 3 -2 5 0 7 , 2 0 0 8 .

[1 0 ] A . D . W yn e r , \ Th e wir e -t a p c h a n n e l" , B ell Syst. Tech. J ., vo l. 5 4 , n o . 8 , p p . 1 3 5 5 -1 3 8 7 ,
1 9 7 5 .

[1 1 ] J. X u , Y . Ca o a n d B . Ch e n , \ Ca p a c it y b o u n d fo r b r o a d c a s t c h a n n e ls wit h c o n ¯ d e n t ia l
m e s s a g e s " , IE E E Trans. Inf. Theory, vo l. 5 5 , n o . 1 0 , p p . 4 5 2 9 -4 5 4 2 , 2 0 0 9 .