D:\sbornik\...\02\Article.DVI


Mathematical Problems of Computer Science 37, 17{24, 2012.

On the Shannon Cipher System with Cor r elated

Sour ce Outputs and Guessing Wir etapper

E avesdr oping thr ough a N oisy Channel

Tig r a n Ma r g a r ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mail: martigranm@gmail.com

Abstract

In this paper the Shannon cipher system with discrete memoryless correlated
sources is considered. The wiretapper gains the noisy version of the cryptogram
through the memoryless noisy channel and tries to guess the secret information which is
related to the encrypted plaintext. The security level of the encryption system is mea-
sured by the expected number of wiretapper's guesses. The upper and lower bounds
are obtained for the guessing rate.

Refer ences

[1 ] J. L . Ma s s e y, \ Gu e s s in g a n d e n t r o p y" , P roceedings of the 1994 IE E E International
Symp. Inform. Theory ( Tr o n d h e im , N o r wa y, 1 9 9 4 ) , p . 2 0 4 .

[2 ] E . A r ika n , \ On t h e a ve r a g e n u b e r o f g u e s s e s r e qu ir e d t o d e t e r m in e t h e va lu e o f a
r a n d o m va r ia b le " , Transactions of the 12th P rague Conference on Information Theory,
Statistical D ecision F unction and R andom P rocesses, p p . 2 0 -2 3 , 1 9 9 4 .

[3 ] E . A r ika n , \ A n in e qu a lit y o n g u e s s in g a n d it s a p p lic a t io n t o s e qu e n t ia l d e c o d in g " , IE E E
Trans. Inform. Theory, vo l. 4 2 , n o . 1 , p p . 9 9 -1 0 5 , 1 9 9 6 .

[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 Trans. Inform. The-
ory, vo l. 4 4 , n o . 3 , p p . 1 0 4 1 -1 0 5 6 , 1 9 9 8 .

[5 ] E . A r ika n a n d N . Me r h a v,\ Jo in t s o u r c e -c h a n n e l c o d in g a n d g u e s s in g wit h a p p lic a t io n
t o s e qu e n t ia l d e c o d in g " , IE E E Trans. Inform. Theory, vo l. 4 4 , n o . 5 , p p . 1 7 5 6 -1 7 6 9 ,
1 9 9 8 .

[6 ] 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 Trans. Inform. Theory, vo l. 4 5 , n o . 6 , p p . 1 8 6 0 -1 8 6 6 , 1 9 9 9 .

[7 ] E . A r ika n , \ Gu e s s in g a n d c r yp t o lo g y" , in \ A s p e c t s o f N e t wo r k a n d In fo r m a t io n S e c u -
r it y" , N A TO S c ie n c e fo r P e a c e a n d S e c u r it y, s e r ie s D : In fo r m a t io n a n d Co m m u n ic a t io n
S e c u r it y, IOS P r e s s , vo l. 1 7 , p p . 2 1 1 { 2 1 7 , 2 0 0 8

[8 ] 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 " , P roceedings of the
2002 IE E E Int. Symp. Inform. Theory ( L a u s a n n a , S wit z e r la n d ) , p . 3 2 4 .

1 7



1 8 On the Shannon Cipher System with Correlated Source Outputs and Guessing Wiretapper

[9 ] 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 \ A s p e c t s
o f N e t wo r k a n d In fo r m a t io n S e c u r it y" , N A TO S c ie n c e fo r P e a c e a n d S e c u r it y, s e r ie s D :
In fo r m a t io n a n d Co m m u n ic a t io n S e c u r it y, IOS P r e s s , vo l. 1 7 , p p . 2 4 8 { 2 6 0 , 2 0 0 8 .

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

[1 1 ] D . Ma lo n e a n d W . G. S u lliva n , \ Gu e s s wo r k a n d e n t r o p y" , IE E E Trans. Inform. Theory,
vo l. 5 0 , n o . 3 , p p . 5 2 5 -5 2 6 , 2 0 0 4 .

[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 , \ 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 in g t h r o u g h a n o is y c h a n n e l" , Transactions of IIAP of NAS of R A
, M athematical P roblems of Computer Science, vo l. 3 5 , p p . 7 0 -7 6 , 2 0 1 1 .

[1 3 ] 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 CSIT 2011, p p . 1 2 5 { 1 2 8 , Y e r e va n 2 0 1 1 .

[1 4 ] 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 5 ] T. M. Co ve r a n d J. A . Th o m a s , E lements of Information Theory, N e w Y o r k: W ile y,
2 0 0 6 .

¶áõß³ÏáÕ ·³Õïݳ·áÕÇ ³éϳÛáõÃÛ³Ùµ ³ÕÙÏáï ϳåáõÕáí ¨
³ÕµÛáõñÇ Ñ³ñ³µ»ñ³Ïóí³Í ѳÕáñ¹³·ñáõÃÛáõÝÝ»ñáí Þ»ÝáÝÛ³Ý

ͳÍϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·Ç Ù³ëÇÝ

î. سñ·³ñÛ³Ý

²Ù÷á÷áõÙ

Ðá¹í³ÍáõÙ ¹Çï³ñÏí»É ¿ Áݹѳï, ³é³Ýó ÑÇßáÕáõÃÛ³Ý Ñ³ñ³µ»ñ³Ïóí³Í ³ÕµÛáõñÝ»ñáí
Þ»ÝáÝÛ³Ý Í³Íϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·Á: ¶³Õïݳ·áÕÁ ëï³ÝáõÙ ¿ ·³Õïݳ·ñÇ ³Õ³-
í³Õí³Í ï³ñµ»ñ³ÏÁ ¨ Ó·ïáõÙ ·áõß³Ï»É ·³ÕïÝÇ ï»Õ»ÏáõÃÛáõÝÁ, áñÁ ϳåí³Í ¿
ͳÍϳ·ñí³Í ³ÛÉ Ñ³Õáñ¹³·ñáõÃÛ³Ý Ñ»ï: ̳Íϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·Ç ·³ÕïÝÇáõÃÛ³Ý
³ëïÇ׳ÝÁ ã³÷íáõÙ ¿ ·³Õïݳ·áÕÇ ·áõß³ÏáõÙÝ»ñÇ ùÝ³Ï³Ç ëå³ë»ÉÇáí: êï³óí»É »Ý
í»ñÇÝ ¨ ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñ Ïé³ÑÙ³Ý ³ñ³·áõÃÛ³Ý Ñ³Ù³ñ:

Î øåííîíîâñêîé ñåêðåòíîé ñèñòåìå ñ êîððåëèðîâàííûìè
ñîîáùåíèÿìè èñòî÷íèêà è óãàäûâàþùèì íàðóøèòåëåì

ïîäñëóøèâàþùèì ÷åðåç êàíàë ñ øóìîì
Ò. Ìàðãàðÿí

Àííîòàöèÿ

 ñòàòüå ðàññìàòðèâàåòñÿ øåííîíîâñêàÿ ñåêðåòíàÿ ñèñòåìà ñ äèñêðåò-
íûìè èñòî÷íèêàìè áåç ïàìåòè. Íàðóøèòåëü ïîëó÷àåò çàøóìëåííóþ
âåðñèþ êðèïòîãðàììû ÷åðåç êàíàë áåç ïàìÿòè è ñòðåìèòñÿ óãàäàòü



T. Margaryan 1 9

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