D:\sbornik\...\tpel.DVI


Mathematical Problems of Computer Science 35, 70{76, 2011.

T he Shannon Cipher System With a Guessing

Wir etapper E avesdr oping T hr ough a N oisy Channel

E vg u e n i A . H a r o u t u n ia n a n d Tig r a n M. Ma r g a r ya n

Institute for Informatics and Automation Problems of NAS of RA

e-mail: eghishe@sci.am

Abstract

In this paper we study the processes in the Shannon cipher system with discrete
memoryless source and a guessing wiretapper. The wiretapper observes a cryptogram
of M -vector ciphered messages passed through the noisy channel and tries to guess the
secret plaintext with length N. The security of encryption system is measured by the
average number of guesses needed for the wiretapper to uncover the plaintext. The
problem was suggested by Arikan and Merhav as a generalization of their result for
noiseless channel to wairtapper.

Refer ences

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

[2 ] E . A r ika n a \ On t h e A ve r a g e N u b e r o f Gu e s s e s R e qu ir e d t o D e t e r m in e t h e V a 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 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 .

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

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

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

[7 ] 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 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
wit h r e s p e c t t o ¯ d e lit y a n d r e lia b ilit y c r it e r ia " , P roceedings of the Third Conference on
Computer Science and Information Technologies ( Y e r e va n , A r m e n ia , 2 0 0 1 ) , p p . 2 1 5 -2 1 9 .

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

7 0



E. Haroutunian, T. Margaryan 7 1

[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, vo l. 1 7 , p p . 2 4 8 { 2 6 0 , IOS P r e s s , 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 ] 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
Trans. on Inform. Theory, vo l. 2 3 , n o . 3 , p p . 2 8 9 -2 9 9 , 1 9 7 7 .

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

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

[1 5 ] A . S g a r r o , " E r r o r P r o b a b ilit ie s fo r S im p le S u b s t it u t io n Cip h e r s " , IE E E Trans. Inform.
Theory, vo l. 2 9 , n o . 2 , p p . 1 9 0 -1 9 7 , 1 9 8 3 .

[1 6 ] A . S g a r r o , \ E xp o n e n t ia l-t yp e p a r a m e t e r s a n d S u b s t it u t io n Cip h e r s " , P roblems of Con-
trol and Inform. Theory, vo l. 1 4 ( 5 ) , p p . 3 9 3 -4 0 3 , 1 9 8 5 .

Þ»ÝáÝÛ³Ý Í³Íϳ·ñÙ³Ý Ñ³Ù³Ï³ñ·áõÙ ·³Õïݳ·áÕÇ ·áõß³ÏáõÙÁ
³ÕÙÏáï ϳåáõÕáí

º. гñáõÃÛáõÝÛ³Ý ¨ î. سñ·³ñÛ³Ý

²Ù÷á÷áõÙ

Ðá¹í³ÍáõÙ ÉáõÍí³Í ¿ Ø»ñѳíÇ ¨ ²ñÇϳÝÇ ÏáÕÙÇó ³é³ç³¹ñí³Í ËݹÇñÁ:
¸Çï³ñÏí³Í ¿ ѳï¨Û³É ѳٳϳñ·Á. ͳÝÇãÁ µ³Ý³Éáõ û·ÝáõÃÛ³Ùµ ͳÍϳ·ñáõÙ ¿
ѳÕáñ¹³·ñáõÃÛáõÝÁ ¨ ³Ý³ÕÙáõÏ Ï³åáõÕáí áõÕ³ñÏáõÙ ¿ ûñÇÝ³Ï³Ý Ñ³ë»³ïÇñáçÁ,
áñÇÝ áõÕ³ñÏáõÙ ¿ ݳ¨ µ³Ý³ÉÇÝ Ù»Ï ³ÛÉ ³Ý³ÕÙáõÏ, å³ßïå³Ýí³Í ϳåáõÕáí:
¶³Õïݳ·áÕÁ, û·ïí»Éáí ³ÕÙÏáï ϳåáõÕáõó, ëï³Ý³Éáí ͳÍϳ·ÇñÁ, Ó·ïáõÙ ¿
í»ñÍ³Ý»É Ñ³Õáñ¹³·ñáõÃÛáõÝÁ ѳçáñ¹³Ï³Ý ·áõß³ÏáõÙÝ»ñÇ ÙÇçáóáí:

Ðá¹í³ÍáõÙ ëï³óí³Í ¿ Ïé³ÑÙ³Ý ³ñ³·áõÃÛ³Ý ·Ýѳï³Ï³ÝÝ»ñÁ: