D:\sbornik\...\Tigran_2014.DVI


Mathematical Problems of Computer Science 41, 47{54, 2014.

T he Shannon Cipher System With Cor r elated Sour ce

Outputs and Wir etapper Guessing Subject to

Distor ion

Tig r a n M. Ma r g a r ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: tigran@ipia.sci.am

Abstract

The Shannon cipher system with discrete memoryless sources is considered. The
wiretapper gains the cryptogram through the public noiseless channel and tries to guess
the secret information which is related to the encrypted plaintext. It is assumed that at
each step of sequential guesses the wiretapper has a testing mechanism to identify the
secret message within the given distortion level. The security level of the encryption
system is measured by the guessing rate which is the highest asymptotic exponential
growth rate of the expected number of guesses. The estimations of guessing rate are
obtained.

Keywords: Shannon cipher system, Correlated sources, Guessing rate.

1 . In t r o d u c t io n

Th e t h e o r e t ic a l s e c r e c y o f S h a n n o n s̀ m o d e l o f c ip h e r s ys t e m ( S CS ) is t r a d it io n a lly m e a s u r e d
b y equivocation [1 ]. In m o s t o f wo r ks in t h is a r e a it is s u p p o s e d t h a t wir e t a p p e r h a s e xa c t ly
o n e c h a n c e t o e s t im a t e t h e p la in t e xt . S h a n n o n a ls o g a ve t h e id e a o f p r a c t ic a l s e c r e c y, wh ic h
is t h e a ve r a g e a m o u n t o f wo r k r e qu ir e d t o b r e a k t h e ke y. H e llm a n t o o k o n e s t e p fo r wa r d
in p r a c t ic a l ( o r c o m p u t a t io n a l) s e c r e c y, p r o p o s e d t o m e a s u r e t h e d e g r e e o f s e c u r it y o f t h e
c ip h e r s ys t e m in t e r m s o f t h e e xp e c t e d n u m b e r o f ke y-p la in t e xt c o m b in a t io n s n e e d e d t o
e xp la in t h e g ive n c ip h e r t e xt [2 ]. Me r h a v a n d A r ika n s u g g e s t e d a n o t h e r s e c u r it y c r it e r io n fo r
t h e S CS , guessing exponent, wh ic h is t h e h ig h e s t a s ym p t o t ic e xp o n e n t ia l g r o wt h r a t e o f t h e
m o m e n t o f t h e n u m b e r o f g u e s s e s [3 ]. Th e g u e s s in g e xp o n e n t fo r e xt e n d e d S CS m o d e ls wa s
e xp lo r e d in t h e s e wo r ks : t h e S CS wit h c o r r e la t e d s o u r c e o u t p u t s wa s s t u d ie d b y H a ya s h i
a n d Y a m a m o t o [4 ] a n d wit h g e n e r a l s o u r c e s wa s s t u d ie d b y H a n a wa l a n d S u n d a r e s a n [5 ].
Th e S CS wit h d is t o r t io n a n d r e lia b ilit y r e qu ir e m e n t s wa s in ve s t ig a t e d b y H a r o u t u n ia n a n d
Gh a z a r ya n [6 , 7 ]. W e h a ve e xa m in e d t h e guessing rate, wh ic h is t h e h ig h e s t a s ym p t o t ic
e xp o n e n t ia l g r o wt h r a t e o f t h e e xp e c t e d n u m b e r o f g u e s s e s in m o d e ls : t h e S CS wit h a n o is y
c h a n n e l t o t h e wir e t a p p e r [8 , 9 ], t h e S CS wit h t h e c o r r e la t e d s o u r c e o u t p u t s a n d t h e n o is y
c h a n n e l [1 0 , 1 1 ], t h e S CS wit h t h e d is t o r t io n a n d t h e n o is y c h a n n e l [1 2 , 1 3 ].

In t h is p a p e r we s t u d y t h e c o m b in e d m o d e l o f t h e S CS c o n s id e r e d in t h e p a p e r s [6 ] a n d
[4 ]. Th e c r yp t o g r a p h ic s ys t e m d e p ic t e d in Fig . 1 is t h e S CS wit h c o r r e la t e d s o u r c e s . Th e

4 7



4 8 The Shannon Cipher System With Correlated Source Outputs and Wiretapper Guessing Subject

m e m o r yle s s s o u r c e g e n e r a t e s m u t u a lly c o r r e la t e d m e s s a g e s o n e o f wh ic h is s e c r e t a n d t h e
o t h e r m u s t b e t r a n s m it t e d t o t h e le g it im a t e r e c e ive r via a p u b lic c h a n n e l. Th e a d ve r s a r y
m a y g a in a t r a n s m it t e d m e s s a g e c o n t a in in g r e le va n t in fo r m a t io n a b o u t a s e c r e t m e s s a g e ,
t h e r e fo r e , it is d e s ir a b le t o t r a n s m it it a ft e r c ip h e r in g e ve n if it is n o t s e c r e t . Th e t r a n s m it t e r
e n c r yp t s t h e p la in t e xt u s in g t h e ke y g e n e r a t e d b y t h e m e m o r yle s s ke y s o u r c e . Th e ke y is a ls o
c o m m u n ic a t e d t o t h e d e c r yp t e r b y a s p e c ia l s e c u r e c h a n n e l. A ft e r c ip h e r in g t h e c r yp t o g r a m
is s e n t o ve r a p u b lic c h a n n e l t o a le g it im a t e r e c e ive r , wh o c a n r e c o ve r t h e o r ig in a l p la in t e xt
u s in g t h e c r yp t o g r a m a n d t h e s a m e ke y. N o t kn o win g t h e ke y, t h e wir e t a p p e r t h a t e a ve s d r o p s
o n t h e p u b lic c h a n n e l a im s t o g u e s s t h e s e c r e t m e s s a g e r e la t e d t o t h e c r yp t o g r a m . It is
a s s u m e d t h a t t h e wir e t a p p e r kn o ws t h e s o u r c e d is t r ib u t io n s a n d e n c r yp t io n fu n c t io n s a n d
t r ie s t o r e c o n s t r u c t t h e s o u r c e s e c r e t m e s s a g e wit h in s o m e g ive n d is t o r t io n m e a s u r e a n d
d is t o r t io n le ve l.

X; Y

U

X̂

Z Y
S ou r ce

Key sou r ce

-
C ip h er er

fN (Y; U)

6

Decip h er er

f
¡1
N

(Z; U)

6

- Legitim ate
r eceiv er

6

Gu esser W ir etap p er

-

-

Fig. 1. The Shannon cipher system with correlated source outputs.

Fo r a n a p p r o xim a t ive r e c o n s t r u c t io n o f a s e c r e t m e s s a g e t h e wir e t a p p e r m a ke s s e qu e n t ia l
g u e s s e s , e a c h t im e a p p lyin g a t e s t in g m e c h a n is m b y wh ic h h e c a n le a r n wh e t h e r t h e e s t im a t e
is s u c c e s s fu l o r n o t a n d s t o p s wh e n t h e a n s we r is a ± r m a t ive . Ou r g o a l is t o e s t im a t e t h e
guessing rate, wh ic h c h a r a c t e r iz e t h e s e c r e c y le ve l o f t h e s ys t e m .

2 . S ys t e m Mo d e l a n d D e ¯ n it io n s

W e d e n o t e t h e R V b y c a p it a l le t t e r s , t h e r a n d o m ve c t o r b y b o ld c a p it a l le t t e r s , a n d t h e ir
r e a liz a t io n s a r e d e n o t e d b y lo we r -c a s e le t t e r s , r e s p e c t ive ly. In t h e s ys t e m s h o wn in Fig . 1 .
t h e s o u r c e a n d t h e ke y-s o u r c e a r e s t a t io n a r y a n d m e m o r yle s s .

Th e s o u r c e is a s s u m e d t o g e n e r a t e d is c r e t e m u t u a lly c o r r e la t e d r a n d o m ve c t o r s X a n d
Y wh ic h c o n s is t o f d is c r e t e , in d e p e n d e n t , id e n t ic a lly d is t r ib u t e d ( i.i.d .) r a n d o m va r ia b le s
( R V s ) ( X1; X2; : : : ; XN ) a n d ( Y1; Y2; : : : ; YN ) . X is s e c r e t a n d Y m u s t b e s e n t t o a le g it im a t e
r e c e ive r . Y h a s a p r o b a b ilit y d is t r ib u t io n ( P D ) P ¤ = fP ¤ ( y ) ; y 2 Yg a n d X h a s a c o n d it io n a l
P D V ¤ = fV ¤ ( xjy ) ; x 2 ^X ; y 2 Yg wh e r e X a n d Y a r e t h e ¯ n it e a lp h a b e t s o f s o u r c e . Th e
jo in t P D o f t h e p a ir ( X; Y ) is P ¤ ± V ¤ = fP ¤ ± V ¤ ( x; y ) = P ¤ ( y ) V ¤ ( xjy ) ; y 2 Y; x 2 X g a n d
t h e m a r g in a l P D o f X is P ¤V ¤ = fP ¤V ¤ ( x ) = P

y2Y
P ¤ ( y ) V ¤ ( xjy ) ; x 2 X g:

Th e ke y-s o u r c e g e n e r a t e s t h e r a n d o m ve c t o r U = ( U1; U2; : : : ; UK ) o f K p u r e ly r a n d o m
b it s in d e p e n d e n t o f ( X; Y ) . U is u s e d fo r e n c r yp t io n a n d a ls o is s e n t t o le g it im a t e r e c e ive r
b y a s p e c ia l s e c u r e c h a n n e l.

W e e n c r yp t o n ly Y u s in g t h e ke y U b y t h e e n c r yp t io n fu n c t io n fN : YN £ U K ! Z¤
wh e r e Z is t h e c r yp t o g r a m a lp h a b e t . A ft e r c ip h e r in g we o b t a in a r a n d o m ve c t o r Z ( m a y h a ve
va r ia b le le n g t h d e p e n d in g o n N a n d K ) wh ic h is s e n t via a p u b lic c h a n n e l t o a le g it im a t e



T. Margaryan 4 9

r e c e ive r . Th is e n c r yp t io n fu n c t io n is a s s u m e d t o b e c o n ve r t ib le p r o vid in g t h e g ive n ke y,
i.e . t h e r e e xis t s t h e d e c r yp t io n fu n c t io n f¡1N : Z¤ £ U K ! YN wh ic h a llo ws t h e le g it im a t e
r e c e ive r t o r e c o ve r t h e o r ig in a l Y. Th e wir e t a p p e r g e t s t h e c r yp t o g r a m Z b y t h e p u b lic
n o is e le s s c h a n n e l.

In t h is t a s k it is a llo we d fo r wir e t a p p e r t o r e c o ve r t h e o r ig in a l s e c r e t m a s s a g e wit h s o m e
a c c e p t a b le d e via t io n . D e n o t e va lu e s o f t h e R V X̂ b y t h e x̂ r e p r e s e n t in g t h e r e c o n s t r u c t io n b y
t h e wir e t a p p e r o f t h e s o u r c e s e c r e t m e s s a g e wit h va lu e s in t h e ¯ n it e wir e t a p p e r r e p r o d u c t io n
a lp h a b e t ^X , in g e n e r a l, d i®e r e n t fr o m X .

W e c o n s id e r a s in g le -le t t e r d is t o r t io n m e a s u r e b e t we e n t h e s o u r c e a n d t h e wir e t a p p e r
r e p r o d u c t io n m e s s a g e s : d : X £ ^X ! [0 ; 1 ) : Th e d is t o r t io n m e a s u r e b e t we e n t h e ve c t o r
x 2 X N a n d a wir e t a p p e r r e p r o d u c t io n ve c t o r x̂ 2 ^X N is d e ¯ n e d a s t h e a ve r a g e o f t h e
c o m p o n e n t d is t o r t io n s :

d( x; x̂ )
4
= N¡1

NX

n=1

d( xn; x̂n ) :

Th e wir e t a p p e r g e t t in g t h e c r yp t o g r a m z p r o d u c e s s o m e g u e s s in g s t r a t e g y gN =
fx̂1 ( z ) ; x̂2 ( z ) ; ¢ ¢ ¢g u n t il s o m e ve c t o r x̂ is fo u n d . W e s a y t h a t t h e g u e s s in g s t r a t e g y is ¢ -
a c h ie va b le if t h e r e e xis t s s o m e j s u c h t h a t P rfd( X; x̂j ( z ) ) · N ¢ g = 1 ( s e e [1 4 ]) . L e t
GNf;g ( X̂jZ) b e a n u m b e r o f g u e s s e s n e e d e d fo r t h e wir e t a p p e r t o r e p r o d u c e t h e x̂ b y t h e
s t r a t e g y gN .

De¯nition 1: The key rate RK of the key source is de¯ned by RK = N
¡1 lo g 2 K = K=N.

De¯nition 2: The ¢ -achievable guessing rate R ( P ¤; V ¤; RK ; ¢ ) of this system is de¯ned by

R( P ¤; V ¤; RK ; ¢ ) = lim
N !1

s u p
fN

in f
gN

1
N

lo g E [GNf;g ( X̂jZ) ];

where E [GNf;g ( X̂jZ) ] is the expectation of GNf;g ( X̂jZ) .

W e a p p ly t h e m e t h o d o f t yp e s a n d c o ve r in g le m m a ( [1 5 ], [1 6 ]. Th e t yp e P o f ve c t o r y =
( y1; : : : ; yN ) 2 YN is a P D P = fP ( y ) = N ( yjy ) =N; y 2 Yg, wh e r e N ( yjy ) is t h e n u m b e r o f
r e p e t it io n s o f t h e s ym b o l y a m o n g y1; : : : ; yN . Th e s e t o f ve c t o r s y o f t yp e P is d e n o t e d b y
T NP ( Y ) . Th e s e t o f a ll P D o n Y is d e n o t e d b y P ( Y ) a n d t h e s u b s e t o f P ( Y ) c o n s is t in g o f
t h e p o s s ib le t yp e s o f s e qu e n c e s y 2 YN is d e n o t e d b y PN ( Y ) .

W e d e n o t e e n t r o p y o f R V Y wit h P D P a n d , r e s p e c t ive ly, r e la t ive e n t r o p y b e t we e n P
a n d P ¤ a s fo llo ws

HP ( Y )
4
= ¡

X

y2Y
P ( y ) lo g P ( y ) ;

D ( P jjP ¤ ) 4=
X

y2Y
P ( y ) lo g

P ( y )

P ¤ ( y )
:

Th e jo in t t yp e o f ve c t o r y 2 YN a n d z 2 ZM is t h e P D fM ( y; zjy; z ) =M; y 2 Y; z 2 Zg,
wh e r e M ( y; zjy; z ) is t h e n u m b e r o f o c c u r r e n c e s o f p a ir s ym b o ls ( y; z ) in t h e p a ir o f ve c t o r s
( y; z ) .

W e s a y t h a t t h e c o n d it io n a l t yp e o f x fo r t h e g ive n y is P D V = fV ( xjy ) ; x 2 X ; y 2 Yg
if N ( y; xjy; x) = N ( yjy ) V ( xjy ) fo r a ll y 2 Y; x 2 X . Th e s e t o f a ll s e qu e n c e s x 2 X N o f t h e
c o n d it io n a l t yp e V fo r t h e g ive n y 2 T NP ( Y ) is d e n o t e d b y T NP;V ( Xjy ) a n d c a lle d t h e V -s h e ll
o f y . V N ( X ; P ) is t h e s e t o f a ll p o s s ib le V -s h e lls o f y o f t yp e P .



5 0 The Shannon Cipher System With Correlated Source Outputs and Wiretapper Guessing Subject

Fo r t h e g ive n P D s P ¤ a n d P o f Y , c o n d it io n a l P D s V ¤ a n d V o f X fo r t h e g ive n Y
c o n d it io n a l e n t r o p y o f R V X fo r t h e g ive n R V Y is d e ¯ n e d b y

HP;V ( XjY )
4
= ¡

X

y2Y;x2X
P V ( x ) lo g V ( xjy ) ;

t h e r e la t ive d ive r g e n c e b e t we e n jo in t P D s P ± V a n d P ¤ ± V ¤ is d e ¯ n e d b y

D ( P ± V kP ¤ ± V ¤ ) 4=
X

y2Y;x2X
P ( y ) V ( xjy ) lo g P ( y ) V ( xjy )

P ¤ ( y ) V ¤ ( xjy ) :

L e t P V = Q = fQ ( x) ; x 2 X g b e a P D o n X a n d W = fW ( x̂ j x ) ; x 2 X ; x̂ 2 ^X g b e
a c o n d it io n a l P D o n ^X fo r t h e g ive n x, t h e n t h e m u t u a l in fo r m a t io n b e t we e n X a n d X̂ is
d e ¯ n e d a s

IQ;W ( X ^ X̂ ) =
X

x;x̂

Q ( x ) W ( x̂ j x) lo g W ( x̂ j x )P
x

Q ( x) W ( x̂ j x ) :

Th e r a t e -d is t o r t io n fu n c t io n fo r a s o u r c e wit h P D Q a n d d is t o r t io n le ve l ¢ is e qu a l t o

R( Q; ¢ ) = m in
W 2W (Q;¢ )

IQ;W ( X ^ X̂ ) ; ( 1 )

wh e r e W ( Q; ¢ ) is a s e t o f c o n d it io n a l P D s W s a t is fyin g t h e fo llo win g c o n d it io n

E Q; W d ( X ; X̂ ) =
X

x;x̂

Q ( x ) W ( x̂ j x ) d ( x ; x̂ ) · ¢:

W e will u s e t h e fo llo win g in e qu a lit ie s a n d c o ve r in g le m m a ( [1 5 ], [1 6 ])

jQN ( X ) j < ( N + 1 ) jX j; ( 2 )

jV N ( X ; P ) j < ( N + 1 ) jYjjX j; ( 3 )
jT NP;V ( Xjy ) j · e xp fNHP;V ( XjY ) g; ( 4 )

P ¤ ± V ¤fT NP;V ( X; Y ) g · e xp f¡ND ( P ± V kP ¤ ± V ¤ ) g: ( 5 )
W e wr it e f ( N ) = o( N ) a s N ! 1 t o m e a n t h a t lim

N!1
f ( N ) =N = 0 :

Lemma 1: F or every type Q 2 QN ( X ) and distortion level ¢ there exists a collection of
vectors L ( N; Q; ¢ ) 2 ^X N which covers T NQ ( X ) , such that for every vector x 2 T NQ ( X )

m in
x̂2L (N ; Q ;¢)

d( x; x̂) · N ¢ ;

and
lo g jL ( N; Q; ¢ ) j = NR ( Q; ¢ ) + o( N ) : ( 6 )

W e a ls o u s e t h e fo llo win g n o t a t io n s

h( P; V; RK ; ¢ ) = m in fR ( P; ¢ ) ; HP;V ( XjY ) + RKg;

h( P; V; RK ) = m in fHP V ( X ) ; HP;V ( XjY ) + RKg
a n d

h( P; RK ; ¢ ) = m in fR ( P; ¢ ) ; RKg:



T. Margaryan 5 1

3 . Fo r m u la t io n o f R e s u lt

In t h e fo llo win g t h e o r e m t h e u p p e r a n d lo we r b o u n d s fo r t h e ¢ -a c h ie va b le g u e s s in g r a t e a r e
p r e s e n t e d .

T heor em 1: F or the given P D P ¤, conditional P D s V ¤, and any key rate RK , the following
estimates are valid:

R( P ¤; V ¤; RK ; ¢ ) · m a x
P;V

[h ( P; V; RK ; ¢ ) ¡ D ( P ± V kP ¤ ± V ¤ ) ];

R( P ¤; V ¤; RK ; ¢ ) ¸ m a x
P

[h( P; RK ; ¢ ) ¡ D ( P kP ¤ ) ]:

Cor ollar y 1: W hen the source generate only one message (X = Y) we arrive at the result
of Haroutunian [7] if the reliability goes to in¯nity:

R( P ¤; RK ; ¢ ) = m a x
P

[h( P; RK ; ¢ ) ¡ D ( P jjP ¤ ) ]:

Cor ollar y 2: W hen ¢ = 0 we arrive at the result Hayashi and H. Yamamoto [4]:

R( P ¤; V ¤; RK ) = m a x
P;V

[h( P; V; RK ) ¡ D ( P ± V kP ¤ ± V ¤ ) ]:

P r oof of T heor em

L e t t h e p a ir o f ve c t o r s ( x; y ) b e g e n e r a t e d b y t h e s o u r c e h a vin g t h e jo in t t yp e P ± V
( ( x; y ) 2 TP;V ( X; Y ) ) . To b u ild a s t r a t e g y fo r t h e wir e t a p p e r , we c o n s id e r t h e fo llo win g t wo
s t r a t e g ie s gN1 a n d g

N
2 .

Strategy gN1 : Th e s e t X N c a n b e r e p r e s e n t e d a s t h e u n io n o f ve c t o r s o f va r io u s t yp e s

X N =
[

i=1;2;¢¢¢;jQN (X )j
T NQi ( X ) :

Th e wir e t a p p e r s h o u ld r e c o n s t r u c t t h e ve c t o r x b y t h e g ive n d is t o r t io n le ve l ¢ . Th e wir e t a p -
p e r s lig h t s t h e c r yp t o g r a m z a n d in t o e a c h t yp e Q t r ie s t o ¯ n d s o m e x̂ s u c h t h a t d ( x; x̂ ) · N ¢
fo r e ve r y x 2 T NQi ( X ) .

Fo r s im p lic it y o f fo r m u la wr it in g we s h a ll n o t e o n ly i in s t e a d o f Qi.

W e c o n s id e r a g u e s s in g s t r a t e g y t h a t e n u m e r a t e s t h e t yp e s Q fr o m a c c o r d in g t o n o n
d e c r e a s in g va lu e s o f t h e c o r r e s p o n d in g r a t e -d is t o r t io n fu n c t io n s R( Qi; ¢ ) : R( 1 ; ¢ ) ·
R ( 2 ; ¢ ) · : : :.

A c c o r d in g t o t h e le m m a fo r t h e ¯ xe d i t h e wir e t a p p e r r e g a r d le s s o f a r r a n g e m e n t c h o o s e
s u c h a c o lle c t io n o f ve c t o r s fx̂1;i; x̂2;i; :::x̂l;i l = 1 ; 2 ::jL( N; i; ¢ ) jg t h a t c o ve r s T Ni ( X ) . Th e
ve c t o r x b e lo n g s t o T NQ ( X ) a n d , t h e r e fo r e , it is c le a r t h a t in t h is s t r a t e g y gN1 t h e n u m b e r o f
g u e s s e s is b o u n d e d wit h ( 2 ) a n d ( 6 ) in t h e fo llo win g wa y

GNf;g1 ( x̂jz ) ·
X

i:R(i;¢ )·R(Q;¢ )
jL( N; i; ± ) j

· ( N + 1 ) jX j e xp fN ( R( Q; ¢ ) ) + o ( N ) g ( 7 )
= e xp fNR ( Q; ¢ ) + o( N ) g:



5 2 The Shannon Cipher System With Correlated Source Outputs and Wiretapper Guessing Subject

Strategy gN2 : In t h is s u b -s t r a t e g y t h e wir e t a p p e r wa n t s t o ¯ n d x̂ e xa c t ly ( x̂ = x ) . X N
c a n b e r e p r e s e n t e d a s a fa m ily o f ve c t o r s o f va r io u s c o n d it io n a l t yp e s fo r e a c h g ive n ve c t o r
y 2 T NP ( Y ) .

X N =
[

i=1;2;¢¢¢jV N (X ;P )j
T NP;Vi ( Xjy ) :

Th e wir e t a p p e r u s in g a ll ke ys o n c r yp t o g r a m z o b t a in s a ll p o s s ib le fyi; i = 1 ; 2 ::: 2 Kg, a ft e r
t h a t h e t r ie s t o g u e s s x a s s u m in g c o n d it io n a l e n t r o p y fo r t h e g ive n ve c t o r yi in a s c e n d in g
o r d e r ( HP;V1 ( XjY ) · HP;V2 ( XjY ) · ¢ ¢ ¢) t r ie s t o g u e s s x. Th e n u m b e r o f g u e s s e s is b o u n d e d
wit h t h e h e lp o f ( 3 ) a n d ( 4 ) a s fo llo ws

GNf;g2 ( x̂jz ) ·
X

Vj :HP;Vj (XjY )·HP;V (XjY )
jT NP;Vj ( Xjy ) je xp fKg

· ( N + 1 ) jX jjYj e xp fN HP;V ( XjY ) g e xp fN RKg
= e xp fN ( HP;V ( XjY ) + RK ) + o ( N ) g: ( 8 )

Strategy gN3 : Co m b in in g t h e s t r a t e g ie s g
N
1 a n d g

N
2 , we d e ¯ n e a n e w g

N
3 a s fo llo ws

gN3 = ( x̂
1
1; x̂

2
1; x̂

1
2; x̂

2
2 ¢ ¢ ¢ ) :

Th e n , t h e n u m b e r o f g u e s s e s in t h e s t r a t e g y gN3 is n o t m o r e t h a n t wo fo ld t h e s m a lle r n u m b e r
o f g u e s s e s in gN1 a n d g

N
2 . W e c a n o b t a in fr o m ( 7 ) a n d ( 8 )

GNf;g3 ( x̂jz ) · 2 m in [e xp fN R( P; ¢ ) + o ( N ) g;
e xp fN ( HP;V ( XjY ) + RK ) + o( N ) g]

· e xp fNh( P; V; RK ; ¢ ) + o( N ) g: ( 9 )

A p p lyin g t h e in e qu a lit ie s ( 2 ) ,( 3 ) ,( 8 ) ,( 9 ) , t h e e xp e c t a t io n E [GNf;g3 ( X̂jZ ) ] c a n b e b o u n d e d in
t h e fo llo win g wa y

E [GNf;g3 ( X̂jZ ) ]·
X

P;V

e xp f¡ND ( P ± V kP ¤ ± V ¤ ) gGNf;g3 ( x̂jz )

· ( N + 1 ) jYjjX j+jX j e xp f¡N D ( P ± V kP ¤ ± V ¤ ) gGNf;g3 ( x̂jz )
· e xp fN ( h ( P; V; RK ; ¢ ) ¡ D ( P ± V kP ¤ ± V ¤ ) ) + o ( N ) g: ( 1 0 )

S in c e o u r s t r a t e g y is va lid fo r a n y fu n c t io n fN , fr o m t h e in e qu a lit y ( 1 0 ) we o b t a in t h e
u p p e r b o u n d fo r t h e g u e s s in g r a t e

R( P ¤; V ¤; RK ; ¢ ) = lim
N !1

s u p
fN

in f
gN

1

N
lo g E [GNf;g ( X̂jZ ) ]

· lim
N !1

s u p
1

N
lo g E [GNf;g3 ( X̂jZ) ]

· m a x
P;V

( h( P; V; RK ; ¢ ) ¡ D ( P ± V kP ¤ ± V ¤ ) ) :

It is o b vio u s t h a t t h e lo we r b o u n d fo r R( P ¤; RK ; ¢ ) ( [7 ]) is a ls o a lo we r b o u n d fo r
R( P ¤; V ¤; RK ; ¢ )

R( P ¤; V ¤; RK ; ¢ ) ¸ m a x
P

[h( P; RK ; ¢ ) ¡ D ( P jjP ¤ ) ]:

T heor em is pr oved.



T. Margaryan 5 3

Refer ences

[1 ] C. E . S h a n n o n , \ Co m m u n ic a t io n t h e o r y o f s e c r e c y s ys t e m s " , B ell System Thechnical
J ournal, vo l.2 8 , n o . 3 , p p . 5 6 5 -7 1 5 , 1 9 4 9 .

[2 ] M. E . H e llm a n , \ A n e xt e n t io n o f t h e S h a n n o n t h e o r y a p p r o a c h t o c r yp t o g r a p h y" , IE E E
Transactions on Information Theory, vo l. 2 3 , n o . 3 , p p . 2 8 9 { 2 9 4 , 1 9 7 7 .

[3 ] N . Me r h a v a n d E . A r ika n , \ Th e S h a n n o n c ip h e r s ys t e m wit h a g u e s s in g wir e t a p p e r " ,
IE E E Transactions on Information Theory, vo l. 4 5 , n o . 6 , p p . 1 8 6 0 -1 8 6 6 , 1 9 9 9 .

[4 ] Y . H a ya s h i a n d H . Y a m a m o t o , \ Co d in g t h e o r e m s fo r t h e S h a n n o n c ip h e r s ys t e m wit h a
g u e s s in g wir e t a p p e r a n d c o r r e la t e d s o u r c e o u t p u t s " , IE E E Transactions on Information
Theory, vo l. 5 4 , n o . 6 , p p . 2 8 0 8 -2 8 1 7 , Ju n e 2 0 0 8 .

[5 ] M. K . H a n a wa l a n d R . S u n d a r e s a n ,\ Th e S h a n n o n c ip h e r s ys t e m wit h a g u e s s in g wir e -
t a p p e r : Ge n e r a l s o u r c e s " , IE E E Transactions on Information Theory, vo l. 5 7 , n o . 4 ,
p p . 2 5 0 3 { 2 5 1 5 , 2 0 1 1 .

[6 ] E . A . H a r o u t u n ia n a n d A . R . Gh a z a r ya n , \ On t h e S h a n n o n c ip h e r s ys t e m wit h a wir e -
t a p p e r g u e s s in g s u b je c t t o d is t o r t io n a n d r e lia b ilit y r e qu ir e m e n t s " , IE E E -ISIT 2002,
L a u s a n n a , Ju n e 3 0 -Ju ly 5 , p . 3 2 4 , 2 0 0 2 .

[7 ] E . A . H a r o u t u n ia n , \ R e a lib ilit y a p p r o a c h in wir e t a p p e r g u e s s in g t h e o r y" , in \Aspects
of Network and Information Security", NATO Science for P eace and Security, series
D : Information and Communication Security, IOS P r e s s , vo l. 1 7 , p p . 2 4 8 { 2 6 0 , 2 0 0 8 .

[8 ] E . A . H a r o u t u n ia n a n d T. M. Ma r g a r ya n , \ Th e S h a n n o n c ip h e r s ys t e m wit h a g u e s s in g
wir e t a p p e r e a ve s d r o p p in g t h r o u g h a n o is y c h a n n e l" , Transactions of IIAP NAS R A,
M athematical P roblems of Computer Science, vo l. 3 5 , p p . 7 0 -7 6 , 2 0 1 1 .

[9 ] E . A . H a r o u t u n ia n a n d T. M. Ma r g a r ya n , \ Th e S h a n n o n c ip h e r s ys t e m wit h a g u e s s in g
wir e t a p p e r e a ve s d r o p p in g t h r o u g h a n o is y c h a n n e l" , 20th Telecommunication F orum
TE L F OR , S e r b ia , N o ve m b e r 2 0 -2 2 , p p . 5 3 2 -5 3 6 , 2 0 1 2 .

[1 0 ] E . A . H a r o u t u n ia n a n d T. M. Ma r g a r ya n , \ W ir e t a p p e r g u e s s in g b y n o is y c h a n n e l fo r
t h e S h a n n o n c ip h e r s ys t e m wit h c o r r e la t e d s o u r c e o u t p u t s " , P roceedings of International
Conference Computer Science and Information Technologies, p p . 1 2 5 { 1 2 8 , 2 0 1 1 .

[1 1 ] T. Ma r g a r ya n , \ On t h e S h a n n o n c ip h e r s ys t e m wit h c o r r e la t e d s o u r c e o u t p u t s a n d
g u e s s in g wir e t a p p e r e a ve s d r o p p in g t h r o u g h a n o is y Ch a n n e l " , Transactions of IIAP
NAS R A, M athematical P roblems of Computer Science, vo l. 3 7 , p p . 1 7 -2 4 , 2 0 1 2 .

[1 2 ] E . A . H a r o u t u n ia n a n d T. M. Ma r g a r ya n , \ On t h e S h a n n o n Cip h e r S ys t e m wit h N o is y
Ch a n n e l t o t h e W ir e t a p p e r Gu e s s in g S u b je c t t o D is t o r t io n Cr it e r io n " , Annual Session
D edicated to 90 Anniversary of R afael Alexandrian, Y e r e va n , p p . 5 3 { 5 4 , 2 0 1 3 .

[1 3 ] T. M. Ma r g a r ya n a n d E . A . H a r o u t u n ia n , \ On t h e S h a n n o n c ip h e r s ys t e m wit h d is t o r -
t io n a n d g u e s s in g wir e t a p p e r e a ve s d r o p p in g t h r o u g h a n o is y c h a n n e l" , P roceedings of
International Conference Computer Science and Information Technologies, p p . 1 1 6 { 1 2 0 ,
2 0 1 3

[1 4 ] E . A r ika n a n d N . Me r h a v, \ Gu e s s in g s u b je c t t o d is t o r t io n " , IE E E Transactions on
Information Theory, vo l. 4 4 , n o . 3 , p p . 1 0 4 1 -1 0 5 6 , 1 9 9 8 .

[1 5 ] I. Cs is z ¶a r a n d J. K Äo r n e r , Information Theory: Coding Theorems for D iscrete M emory-
less Systems, N e w Y o r k: A c a d e m ic , 1 9 8 1 .

[1 6 ] T. M. Co ve r a n d J. A . Th o m a s , E lements of Information Theory,S e c o n d E d it io n , N e w
Y o r k: W ile y, 2 0 0 6 .



5 4 The Shannon Cipher System With Correlated Source Outputs and Wiretapper Guessing Subject

Submitted 10.01.2014, accepted 06.03.2014.

îñí³Í ß»ÕáõÙáí ѳñ³µ»ñ³Ïóí³Í ѳÕáñ¹³·ñáõÃÛáõÝÝ»ñáí
Þ»ÝáÝÛ³Ý Í³Íϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·Á ·áõß³ÏáÕ

·³Õïݳí»ñÉáõÍáÕÇ ³éϳÛáõÃÛ³Ùµ

î. سñ·³ñÛ³Ý

²Ù÷á÷áõÙ

¸Çï³ñÏí»É ¿ ѳñ³µ»ñ³Ïóí³Í ѳÕáñ¹³·ñáõÃÛáõÝÝ»ñáí Þ»ÝáÝÛ³Ý Í³Íϳ·ñÙ³Ý
ѳٳϳñ·Á: ³Õïݳ·áÕÁ ëï³ÝáõÙ ¿ ·³Õïݳ·ÇñÁ ¨ Ó·ïáõÙ ¿ ·áõß³Ï»É ·³ÕïÝÇ
ï»Õ»ÏáõÃÛáõÝÁ, áñÁ ϳåí³Í ¿ ·³Õïݳ·ñÇ Ñ»ï: ºÝó¹ñíáõÙ ¿, áñ ·áõß³ÏÙ³Ý
Ûáõñ³ù³ÝãÛáõñ ù³ÛÉáõÙ ·³Õïݳí»ñÉáõÍáÕÁ áõÝÇ ëïáõ·Ù³Ý ٻ˳ÝǽÙ, Áëï áñÇ
ϳñáÕ ¿ ÇٳݳÉ, û ³ñ¹Ûáù, ·áõß³Ïí³Í ѳÕáñ¹³·ñáõÃÛáõÝÁ µ³í³ñ³ñáõÙ ¿ ïñí³Í
ß»ÕÙ³ÝÁ: ̳Íϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·Ç ·³ÕïÝÇáõÃÛ³Ý ³ëïÇ׳ÝÁ ã³÷íáõÙ ¿ ·áõß³ÏÙ³Ý
³ñ³·áõÃÛ³Ùµ, áñÁ ·áõß³ÏáõÙÝ»ñÇ ù³Ý³ÏÇ ëå³ë»ÉÇ ³Ù»Ý³Ù»Í ³ëÇÙåïáïÇÏ óáõóÇãÝ
¿: ݳѳïí»É ¿ ·³ÕïݳÉëáÕÇ ·áõß³ÏÙ³Ý ³ñ³·áõÃÛáõÝÁ:

Øåííîíîâñêàÿ ñåêðåòíàÿ ñèñòåìà ñ êîððåëèðîâàííûìè
ñîîáùåíèÿìè èñòî÷íèêà ñ çàäàííûì

èñêàæåíèåì è óãàäûâàþùèì íàðóøèòåëåì
Ò. Ìàðãàðÿí

Àííîòàöèÿ

 ñòàòüå ðàññìàòðèâàåòñÿ øåííîíîâñêàÿ ñåêðåòíàÿ ñèñòåìà ñ äèñêðåòíûìè
èñòî÷íèêàìè áåç ïàìÿòè. Íàðóøèòåëü ïîëó÷àåò êðèïòîãðàììó è ñòðåìèòñÿ
óãàäàòü ñåêðåòíóþ èíôîðìàöèþ, ñâÿçàííóþ ñ çàøèôðîâàííûì ñîîáùåíèåì.
Ïðåäïîëàãàòåñÿ, ÷òî íà êàæäîì øàãó íàðóøèòåëü âëàäååò òåñòèðóþùèì
ìåõàíèçìîì, èñõîäÿ èç êîòîðîãî îí ìîæåò óçíàòü óäîâëåòâîðÿåò ëè êðèïòîãðàììà
äàííîìó èñêàæåíèþ. Óðîâåíü ñåêðåòíîñòè êðèïòîãðàôè÷åñêîé ñèñòåìû
èçìåðÿåòñÿ ñêîðîñòüþ óãàäûâàíèÿ, êîòîðàÿ îïðåäåëÿåòñÿ íàèáîëüøèì àñèìòîòè-
÷åñêèì ïîêàçàòåëåì ìàòåìàòè÷åñêîãî îæèäàíèÿ ÷èñëà óãàäûâàíèé íàðóøèòåëÿ.
Îöåíåíà ñêîðîñòü óãàäûâàíèÿ íàðóøèòåëÿ.