Mariam_Haroutunian.DVI


Mathematical Problems of Computer Science 42, 17{27, 2014.

I nfor mation T heor etical Analysis of B iometr ic

Gener ated Secr et Key Shar ing M odel

Ma r ia m E . H a r o u t u n ia n 1 a n d N a r e k S . P a h le va n ya n 2

1Institute for Informatics and Automation Problems of NAS RA
2Gyumri State Pedagogical Institute

e-mail: armar@ipia.sci.am, narek@ravcap.com

Abstract

We investigate the biometric generated secret key sharing system. We consider the
generalization of the secret key rate, studied by Ignatenko and Willems [1]: the notion
of E-achievable secret key rate is introduced. The lower and upper bounds for the
largest E-achievable secret key rate are obtained. When E tends to zero, the limits of
our bounds coincide and are equal to the largest achievable secret key rate stated in
[1].

Keywords: Biometric systems, Generated secret key, E-achievable rate, Achiev-
able secret rate.

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

In r e c e n t ye a r s t h e b io m e t r ic s e c r e c y s ys t e m s a r e b e in g wid e ly u s e d , r a n g in g fr o m b o r d e r
c o n t r o l a t a ir p o r t s t o a c c e s s c o n t r o l in va r io u s s ys t e m s s u c h a s c o m p u t e r lo g -in , ID c a r d s ,
e -p a s s p o r t s . Th e p u r p o s e o f u s in g b io m e t r ic s e c r e c y s ys t e m s is t o a vo id a lo t o f r e la t e d
p r o b le m s wit h t h e u s a g e o f t r a d it io n a l p a s s wo r d s . Fo r in s t a n c e , s im p le p a s s wo r d s c a n b e
e a s ily g u e s s e d o r b r o ke n b y b r u t e -fo r c e a t t a c ks , wh ile m o r e c o m p le x p a s s wo r d s a r e d i± c u lt
t o r e m e m b e r . Fu r t h e r m o r e , wh e n a s in g le p a s s wo r d is c o m p r o m is e d , it m a y o p e n m a n y
o t h e r \ g a t e s " , b e c a u s e m o s t p e o p le u s e t h e s a m e p a s s wo r d fo r a u t h e n t ic a t io n in d i®e r e n t
lo c a t io n s . Fin a lly, a p a s s wo r d c a n b e s h a r e d wit h a n o t h e r p e r s o n a n d t h e r e will b e n o wa y
t o kn o w wh o t h e a c t u a l u s e r is .

Th e a b o ve m e n t io n e d lim it a t io n s c a n b e s o lve d , if t h e b io m e t r ic s e c r e c y s ys t e m s wo u ld
b e u s e d t o a u t h e n t ic a t e a n in d ivid u a l. B e s id e s , t h e a u t h e n t ic a t io n b io m e t r ic s e c r e c y s ys t e m s
c a n b e u s e d in id e n t i¯ c a t io n , e xa m in a t io n s , p a ym e n t p r o c e s s in g s a n d in o t h e r va r io u s a p p li-
c a t io n s . S u c h s ys t e m s a r e m o r e s e c u r e t h a n t h e t r a d it io n a l p a s s wo r d -b a s e d a u t h e n t ic a t io n
s ys t e m s , b e c a u s e t h e b io m e t r ic p r o p e r t ie s c a n n o t b e lo s t o r fo r g o t t e n , t h e y a r e d i± c u lt t o
fa ls ify o r d u p lic a t e , s h a r e , a n d d is t r ib u t e . In m a n y a p p lic a t io n s , s u c h a s , e xa m in a t io n s , t h e
p e r s o n is r e qu ir e d t o b e p r e s e n t a t t h e t im e a n d p o in t o f a u t h e n t ic a t io n . Mo r e o ve r , t h e r e
a r e a c c e s s s c e n a r io s , wh ic h r e qu ir e a p a r t ic ip a t io n o f m u lt ip le p r e vio u s ly r e g is t e r e d u s e r s fo r
a s u c c e s s fu l a u t h e n t ic a t io n o r t o g e t a n a c c e s s g r a n t fo r a c e r t a in e n t it y. Fo r in s t a n c e , t h e r e
a r e c r yp t o g r a p h ic c o n s t r u c t io n s kn o wn a s s e c r e t s h a r in g s c h e m e s , wh e r e a s e c r e t ke y is s p lit
in t o s h a r e s a n d d is t r ib u t e d a m o n g s t t h e u s e r s in s u c h a wa y t h a t it c a n b e r e c o n s t r u c t e d

1 7



1 8 Information Theoretical Analysis of Biometric Generated Secret Key Sharing Model

o n ly wh e n t h e n e c e s s a r y n u m b e r o f s e c r e t ke y h o ld e r s c o m e s t o g e t h e r . Th e r e ve a le d s e c r e t
c a n t h e n b e u s e d fo r e n c r yp t io n o r a u t h e n t ic a t io n . On e o f s u c h a p p lic a t io n s c o u ld b e s h a r in g
o f a b a n k a c c o u n t b y fa m ily m e m b e r s .

H o we ve r , t h e u s a g e o f b io m e t r ic s e c r e c y s ys t e m s h a s it s o wn d is a d va n t a g e s . A s t h e b io -
m e t r ic d a t a a r e g a t h e r e d fr o m in d ivid u a ls u n d e r e n vir o n m e n t a l c o n d it io n s a n d t h e c h a n n e ls
a r e e xp o s e d t o n o is e t h e b io m e t r ic s e c r e c y s ys t e m m a y a c c e p t a n im p o s t o r o r r e je c t a n a u -
t h o r iz e d in d ivid u a l. B a s ic a lly, it 's n o t p o s s ib le t o b u ild a n id e a l b io m e t r ic s e c r e c y s ys t e m , it
c a n b e in fo r m a t io n -t h e o r e t ic a l s e c u r e u p t o a c e r t a in le ve l.
Ig n a t e n ko a n d W ille m s [1 ] h a ve m e n t io n e d t h a t a p e r fe c t s ys t e m fo r a s e c u r e b io m e t r ic a u -
t h e n t ic a t io n h a s t o s a t is fy t h r e e r e qu ir e m e n t s . Fir s t ly, b io m e t r ic d a t a h a ve t o b e p r iva t e ,
t h a t m e a n s t h e r e fe r e n c e in fo r m a t io n s t o r e d in d a t a b a s e s h o u ld n o t r e ve a l t h e a c t u a l b io -
m e t r ic d a t a . S e c o n d ly, r e fe r e n c e d a t a t h a t a r e c o m m u n ic a t e d fr o m a d a t a b a s e t o t h e p la c e
wh e r e a n a c c e s s c a n b e g r a n t e d o r d e n ie d h a ve t o b e fa u lt -t o le r a n t t o e a ve s d r o p p in g . A n d
¯ n a lly r e fe r e n c e d a t a s t o r e d in d a t a b a s e h a ve t o b e r e s ilie n t t o b r u t e -fo r c e a t t a c ks .
N o n e t h e le s s , a s p r a c t ic e s h o ws p e o p le d o n o t fe e l c o m fo r t a b le in p r o vid in g t h e ir b io m e t r ic
in fo r m a t io n t o a la r g e a m o u n t o f o u t wa r d ly s e c u r e d a t a b a s e s , b e c a u s e o n e c a n n o t fu lly t r u s t
t h e s e c u r it y im p le m e n t a t io n s o f t h ir d p a r t ie s , a n o t h e r r e a s o n is t h a t t h e d a t a b a s e m ig h t
b e c o m p r o m is e d fr o m in s id e , wh ic h will a llo w a n o wn e r o f a d a t a b a s e t o m is u s e b io m e t r ic
in fo r m a t io n . A n d ¯ n a lly p e o p le h a ve lim it e d b io m e t r ic r e s o u r c e s , s o \ id e n t it y t h e ft " h a s
m u c h m o r e s e r io u s im p a c t s t h a n a \ s im p le " t h e ft o f a c r e d it c a r d .

In t h is p a p e r we r e vis it t h e p r o b le m o f g e n e r a t in g s e c r e t ke ys fr o m b io m e t r ic d a t a p r o -
vid e d in [1 ]. W e in t r o d u c e t h e n o t io n o f E-a c h ie va b le s e c r e t ke y r a t e a n d o b t a in t h e lo we r
a n d u p p e r b o u n d s fo r t h e la r g e s t E-a c h ie va b le s e c r e t ke y r a t e . W h e n E t e n d s t o z e r o , t h e
lim it s o f o u r r e s u lt s c o in c id e wit h t h e la r g e s t a c h ie va b le s e c r e t ke y r a t e d e ¯ n e d in [1 ].

2 . R e la t e d W o r k

S e c u r it y c o n c e r n s r e la t e d t o t h e u s e o f b io m e t r ic d a t a in d i®e r e n t s e c r e c y s ys t e m s we r e r a is e d
a lo n g t im e a g o . Fr o m t h e in fo r m a t io n -t h e o r e t ic a l p e r s p e c t ive t h e b io m e t r ic s e c r e c y s ys t e m s
we r e s t u d ie d b y O'S u lliva n a n d S c h m id [2 ] a n d W ille m s e t a l [3 ]. W ille m s [3 ] in ve s t ig a t e d t h e
fu n d a m e n t a l p r o p e r t ie s o f t h e b io m e t r ic id e n t ī c a t io n s ys t e m . It h a s b e e n s h o wn t h a t it is
im p o s s ib le t o r e lia b ly id e n t ify m o r e p e r s o n s t h a n c a p a c it y wh ic h is a n in h e r e n t c h a r a c t e r is t ic
o f a n y id e n t ī c a t io n s ys t e m . B y a n a lo g y wit h n o t io n o f E-c a p a c it y o r r a t e -r e lia b ilit y fu n c t io n
in t r o d u c e d fo r d is c r e t e m e m o r yle s s c h a n n e ls b y E . H a r o u t u n ia n [4 ] in [5 ] t h e n e w c o n c e p t o f
id e n t ī c a t io n E-c a p a c it y fo r b io m e t r ic a l id e n t ī c a t io n s ys t e m wa s in t r o d u c e d . Th e a u t h o r s
d e r ive d t h e u p p e r a n d lo we r b o u n d s o f b io m e t r ic id e n t ī c a t io n s ys t e m . L a t e r in [6 ] t h e
a u t h o r s in ve s t ig a t e d t h e r a t e -r e lia b ilit y fu n c t io n fo r b io m e t r ic id e n t i¯ c a t io n p r o t o c o l wit h a
r a n d o m p a r a m e t e r .

Th e p r o b le m o f g e n e r a t in g s e c r e t ke ys fr o m b io m e t r ic d a t a is c lo s e ly r e la t e d t o t h e c o n -
c e p t o f s e c r e t s h a r in g , wh ic h wa s in t r o d u c e d b y Ma u r e r [7 ] a n d b y A h ls we d e a n d Cs is z a r [8 ].
Th is p r o b le m in b io m e t r ic s e t t in g wa s c o n s id e r e d b y Ig n a t e n ko a n d W ille m s [1 ]. U n like in
t r a d it io n a l s e c r e t ke y s h a r in g , wh e r e t h e s e c r e t ke y is b e in g g e n e r a t e d a n d s h a r e d b e t we e n
t e r m in a ls , in b io m e t r ic s e c r e c y s ys t e m s a s e c r e t ke y is g e n e r a t e d d u r in g a n e n r o llm e n t p r o -
c e d u r e in wh ic h t h e b io m e t r ic d a t a a r e o b s e r ve d fo r t h e ¯ r s t t im e . Th e s e c r e t ke y is t o b e
r e c o n s t r u c t e d a ft e r t h e s e b io m e t r ic d a t a a r e o b s e r ve d a g a in , d u r in g a n a t t e m p t t o g e t a n a c -
c e s s . R e lia b le b io m e t r ic s e c r e c y s ys t e m s e xt r a c t h e lp e r d a t a fr o m t h e b io m e t r ic in fo r m a t io n
a t t h e t im e o f e n r o llm e n t , a s b io m e t r ic m e a s u r e m e n t s a r e t yp ic a lly n o is y. Th e s e h e lp e r d a t a



M. Haroutunian and N. Pahlevanyan 1 9

c o n t r ib u t e t o r e lia b le r e c o n s t r u c t io n o f t h e s e c r e t ke y. Th e d e t a ile d d e s c r ip t io n o f t h is m o d e l
is g ive n in t h e n e xt s e c t io n . Mo r e d e t a ile d r e vie w o n in fo r m a t io n -t h e o r e t ic a p p r o a c h e s o f
b io m e t r ic s e c r e c y s ys t e m s c a n b e fo u n d in [9 ].

3 . B io m e t r ic Ge n e r a t e d S e c r e t K e y S h a r in g Mo d e l

B e fo r e we s t a r t in t r o d u c in g t h e m o d e l le t 's d e ¯ n e s o m e c o n ve n t io n s t h a t a r e a p p lie d wit h in
t h is p a p e r . Ca p it a l le t t e r s a r e u s e d fo r r a n d o m va r ia b le s ( R V ) X; Y t a kin g va lu e s in t h e
¯ n it e a lp h a b e t s X ; Y, c o r r e s p o n d in g ly. Th e c a r d in a lit y o f t h e a lp h a b e t X is d e n o t e d b y jX j.
B io m e t r ic g e n e r a t e d s e c r e t ke y s h a r in g is o n e o f t h e a va ila b le m o d e ls o f b io m e t r ic s e c r e t ke y
s h a r in g s ys t e m . Th e m o d e l is r e p r e s e n t e d in Fig u r e 1 .

Fig. 1. Biometric generated secret key sharing model.

Th e m o d e l is b a s e d o n a b io m e t r ic s o u r c e wit h d is t r ib u t io n fQ ( x; y ) ; x 2 X ; y 2 Yg.
Th is s o u r c e p r o d u c e s x ´ xN = ( x1; x2; :::; xN ) o f N s ym b o ls fr o m t h e ¯ n it e a lp h a b e t X a n d
a s e c o n d s e qu e n c e y ´ yN = ( y1; y2; :::; yN ) o f N s ym b o ls fr o m t h e ¯ n it e a lp h a b e t Y. Th e
¯ r s t s e qu e n c e is c a lle d a n e n r o llm e n t s e qu e n c e , a n d t h e s e c o n d s e qu e n c e a n a u t h e n t ic a t io n
s e qu e n c e . Fu r t h e r m o r e , t h e s e c o n d s e qu e n c e Y N is a n o is y ve r s io n o f t h e ¯ r s t s e qu e n c e X N .
L e t u s d e n o t e

Q( x; y ) = Q1 ( x ) Q2 ( yjx ) ; x 2 X ; y 2 Y:
W e a s s u m e t h a t

QN ( x; y ) =
NY

n=1

Q ( xn; yn ) :

Th e n c o n s id e r a n e n c o d e r t h a t e xp lo r e s t h e e n r o lm e n t s e qu e n c e XN . Fr o m t h is s e qu e n c e in
b io m e t r ic g e n e r a t e d s e c r e t ke y s h a r in g m o d e l t h e e n c o d e r g e n e r a t e s a s e c r e t S 2 f1 ; 2 ; :::; jSjg
a n d t h e n a p u b lic h e lp e r -m e s s a g e ( h e lp e r d a t a ) M 2 f 1 ; 2 ; :::; jMjg. Th a t m e a n s t h a t

f ( X N ) = ( S; M ) ;

wh e r e b y f ( ¢ ) we d e n o t e t h e e n c o d e r fu n c t io n . Th e h e lp e r -m e s s a g e is s e n t t o t h e d e c o d e r .
Th e d e c o d e r e xp lo r e s t h e a u t h e n t ic a t io n s e qu e n c e Y N a n d p r o d u c e s a n e s t im a t e Ŝ o f t h e

s e c r e t S u s in g t h e r e c e ive d h e lp e r d a t a M, h e n c e

g ( Y N ; M ) = Ŝ;

wh e r e b y g ( ¢; ¢ ) we d e n o t e t h e d e c o d e r fu n c t io n . Th e c h a n n e l b e t we e n t h e e n c o d e r a n d t h e
d e c o d e r is e xp e c t e d t o b e p u b lic . W e a s s u m e t h a t a n a t t a c ke r h a s a n a c c e s s t o t h a t c h a n n e l,
s o h e c a n s e e a ll t h e p u b lic in fo r m a t io n b u t c a n n o t m o d ify. Th e in fo r m a t io n o u t ° o w is
d e s c r ib e d in t e r m s o f m u t u a l in fo r m a t io n , a n d t h e s iz e o f t h e s e c r e t ke y{ in t e r m s o f e n t r o p y.
Fin g e r p r in t s a n d ir is e s c a n b e m o d e le d a s s u c h b io m e t r ic s o u r c e s .



2 0 Information Theoretical Analysis of Biometric Generated Secret Key Sharing Model

Th e im p o r t a n t p a r a m e t e r s o f a b io m e t r ic s e c r e c y s ys t e m in c lu d e t h e s iz e o f s e c r e t ke y
a n d t h e in fo r m a t io n t h a t t h e h e lp e r d a t a le a k o n t h e b io m e t r ic o b s e r va t io n . Th a t le a k o f
b io m e t r ic in fo r m a t io n is c a lle d a p r iva c y le a ka g e . Th e p r iva c y le a ka g e s h o u ld b e s m a ll, t o
a vo id t h e b io m e t r ic d a t a o f a n in d ivid u a l t o b e c o m e c o m p r o m is e d . Mo r e o ve r , t h e s e c r e t ke y
le n g t h s h o u ld b e la r g e t o m in im iz e t h e p r o b a b ilit y t h a t t h e s e c r e t ke y is g u e s s e d . It is t h e
g o a l o f b o t h s id e s ( e n c o d e r a n d d e c o d e r ) t o p r o d u c e a s e c r e t ke y a s la r g e a s p o s s ib le , t h a t
s a t is i¯ e s t h is c o n d it io n P r fS 6= Ŝg ¼ 0 , t h is m e a n s t h a t p r o b a b ilit y t h a t t h e e s t im a t e d
s e c r e t Ŝ is n o t e qu a l t o t h e g e n e r a t e d s e c r e t S is c lo s e t o z e r o . Th e b io m e t r ic g e n e r a t e d
s e c r e t ke y s h a r in g m o d e l m u s t s a t is fy t h e fo llo win g r e qu ir e m e n t s [1 ]

P r fS 6= Ŝg ¼ 0 ( r e lia b ilit y) ,
1

N
H ( S ) ¼ 1

N
lo g 2 jSj ( s e c r e t u n ifo r m it y) ,

1

N
H ( S ) is a s la r g e a s p o s s ib le ( s e c r e t ke y r a t e ) ,

1

N
I ( S ^ M ) ¼ 0 ( s e c r e c y le a ka g e ) ,

1

N
I ( X N ^ M ) is a s s m a ll a s p o s s ib le ( p r iva c y le a ka g e ) .

H e r e is a d e ¯ n it io n fo r t h e a c h ie va b le s e c r e t ke y r a t e s t a t e d in [1 ]. A s e c r e t ke y r a t e R, fo r
R ¸ 0 , is c a lle d a c h ie va b le if fo r a ll ± > 0 a n d a ll N la r g e e n o u g h , t h e r e e xis t e n c o d e r s a n d
d e c o d e r s s u c h t h a t

P r fS 6= Ŝg · ±;
1

N
H ( S ) + ± ¸ 1

N
lo g 2 jSj ¸ R ¡ ±;

1

N
I ( S ^ M ) · ±:

A h ls we d e a n d Cs is z ¶a r [8 ] p r o p o s e d a n d p r o ve d a t h e o r e m , wh ic h s t a t e d t h a t fo r a s o u r c e
t yp e m o d e l t h e la r g e s t a c h ie va b le s e c r e t ke y r a t e R is e qu a l t o m u t u a l in fo r m a t io n I ( X ^Y ) .
U n like t h e o r ig in a l p r o o f, wh ic h is b a s e d o n s t r o n g t yp ic a lit y, a n o t h e r p r o o f o f t h e s a m e
t h e o r e m , b u t fo r b io m e t r ic g e n e r a t e d s e c r e t m o d e l, u s in g we a k t yp ic a lit y is g ive n in [1 ].
In t h e n e xt s e c t io n we will in t r o d u c e n e w c o n c e p t o f E-a c h ie va b le s e c r e t ke y r a t e , wh ic h
d i®e r s fr o m t r a d it io n a l s e c r e t ke y r a t e b y h a vin g a m o r e s o lid r e qu ir e m e n t a n d e xp o n e n t ia lly
d e c r e a s e s t h e e r r o r p r o b a b ilit y in p r a c t ic e .

4 . E-a c h ie va b le S e c r e t K e y R a t e

De¯nition: A secret key rate R ( E ) , for R ( E ) ¸ 0 , is called E-achievable if for all ± > 0 ,
E > 0 and N large enough, there exists a code such that

P r fS 6= Ŝg · 2 ¡N(E¡±);

1

N
H ( S ) + ± ¸ 1

N
lo g 2 jSj ¸ R ( E ) ¡ ±;

1

N
I ( S ^ M ) · ±:



M. Haroutunian and N. Pahlevanyan 2 1

W e s h a ll u s e t h e fo llo win g P D in t h e fo r m u la t io n o f r e s u lt :

Q1 = fQ1 ( x ) ; x 2 X g ; Q2 = fQ2 ( yjx ) ; y 2 Y; x 2 X g;

P1 = fP1 ( x ) ; x 2 X g ; P2 = fP2 ( yjx ) ; y 2 Y; x 2 X g;
Q = fQ ( x; y ) ; x 2 X ; y 2 Yg ;
P = fP ( x; y ) ; x 2 X ; y 2 Yg:

W e r e fe r t o [4 ] , [1 0 ] , [1 1 ] a n d [1 2 ] fo r n o t io n s o f d ive r g e n c e D ( P jjQ ) , m u t u a l in fo r m a t io n
IP ( X ^ Y ) , in fo r m a t io n -t h e o r e t ic qu a n t it ie s . Th e p r o o fs a r e b a s e d o n t h e m e t h o d o f t yp e s .
W e d e n o t e b y T NP1 ( X ) t h e s e t o f ve c t o r s x o f t yp e P1, b y T

N
P ( X; Y ) t h e s e t o f ve c t o r s ( x; y )

o f t yp e P . W e u s e s o m e kn o wn p r o p e r t ie s [4 ], [1 0 ], [1 1 ], [1 2 ].

Fo r ( x; y ) 2 T NP ( X; Y )

QN ( x; y ) = e xp f¡N ( HP ( X; Y ) + D ( P jjQ ) ) g; ( 1 )
jT NP ( X; Y ) j · e xp fNHP ( X; Y ) g; ( 2 )

QN ( T NP ( X; Y ) ) · e xp f¡N D ( P jjQ ) g; ( 3 )
D ( P jjQ ) = D ( P1jjQ1 ) + D ( P2jjQ2jP1 ) : ( 4 )

Ou r m a in r e s u lt is s t a t e d in t h e fo llo win g t h e o r e m .

T heor em: F or biometric generated-secret model the largest E-achievable secret key rate
R ( E ) is lower bounded by

Rr ( E ) = m in
P :D(P jjQ)·E

jIP ( X ^ Y ) + D ( P jjQ ) ¡ Ej+ ( 5 )

a n d u p p e r b o u n d e d b y

Rsp ( E ) = m in
P :D(P jjQ)·E

IP ( X ^ Y ) : ( 6 )

H e r e t h e n o t a t io n jaj+ is u s e d fo r m a x( a, 0 ) .

Cor ollar y: W hen E ! 0 , the limits of our bounds coincide and are equal to the largest
achievable secret key rate de¯ned in [1]:

lim
E!0

Rr ( E ) = lim
E!0

Rsp ( E ) = IQ ( X ^ Y ) :

5 . P r o o f o f Th e o r e m

P r oof of Upper B ound.
L e t E > 0 a n d t h e e r r o r p r o b a b ilit y s a t is fy t h e c o n d it io n P r fS 6= Ŝg · e xp f¡N ( E ¡± ) g.

It m e a n s t h a t

X

x2X N
QN1 ( x )

1

jSj
X

s2S
QN2

n
Y N ¡ g¡1m ( s)

¯̄
¯xm ( s)

o
· e xp f¡N ( E ¡ ± ) g;



2 2 Information Theoretical Analysis of Biometric Generated Secret Key Sharing Model

wh e r e
g¡1m ( s) = fy : gm ( y ) = sg:

Fo r a n y P we c a n wr it e

X

s2S

X

xm(s)2T NP1 (X)
QN1 ( xm ( s) ) £ QN2

n
T NP ( Y jxm ( s) ) ¡ g¡1m ( s)

¯̄
¯xm ( s)

o
·

jSj e xp f¡N ( E ¡ ± ) g:
QN1 ( xm ( s) ) a n d Q

N
2 ( yjxm ( s) ) a r e c o n s t a n t fo r va r io u s x a n d y o f ¯ xe d t yp e P , h e n c e , we

c a n wr it e X

s2S

X

xm(s)2T NP1 (X)

n¯̄
¯T NP ( Y jxm ( s) )

¯̄
¯ ¡

¯̄
¯T NP ( Y jxm ( s) )

\
g¡1m ( s)

¯̄
¯
o
£

QN1 ( xm ( s) ) £ QN2 ( yjxm ( s) ) · jSj e xp f¡N ( E ¡ ± ) g:
A c c o r d in g t o ( 3 )

X

s2S

X

xm(s)2T NP1 (X)

n¯̄
¯T NP ( Y jxm ( s) )

¯̄
¯ ¡

¯̄
¯T NP ( Y jxm ( s) )

\
g¡1m ( s)

¯̄
¯
o
£

e xp f¡N ( D ( P jjQ ) + HP2 ( Y jX ) ) g · jSj e xp f¡N ( E ¡ ± ) g: ( 7 )
It fo llo ws fr o m t h e d e ¯ n it io n o f d e c o d in g fu n c t io n g t h a t fo r t h e g ive n m t h e s e t s g¡1m ( s) a r e
d is jo in t , t h e r e fo r e X

s2S

¯̄
¯T NP ( Y jxm ( s) )

\
g¡1m ( s)

¯̄
¯ · jT NP ( Y ) j:

Th e n fr o m ( 7 ) we h a ve

X

s2S

¯̄
¯T NP ( Y jxm ( s) )

¯̄
¯ ¡ jSj e xp f¡N ( E ¡ ± ) g

e xp f¡N ( D ( P jjQ ) + HP ( Y jX ) ) g
· jT NP ( Y ) j:

H e n c e ,

jSj · e xp fN IP ( X ^ Y ) g
( N + 1 ) ¡jXjjY j ¡ e xp fN ( D ( P jjQ ) ¡ E ¡ ± ) g:

Th e r ig h t -h a n d s id e o f t h is in e qu a lit y c a n b e m in im iz e d b y t h e c h o ic e o f P ke e p in g t h e d e -
n o m in a t o r p o s it ive , wh ic h t a ke s p la c e fo r la r g e N, wh e n D ( P jjQ) · E ¡ ±:

Achievability par t of theor em.

Code Constr uction. W e c o n s id e r t h o s e t yp e s P t h a t D ( P jjQ ) · E, fr o m ( 4 ) it fo llo ws
t h a t

D ( P1jjQ1 ) · E a n d D ( P2jjQ2jP1 ) · E:
L e t u s d e n o t e

T NQ1 ( E ) =
[

P1:D(P1jjQ1)·E
T NP1 ( X ) ;

T NQ ( E ) =
[

P :D(P jjQ)·E
T NP ( X; Y ) :



M. Haroutunian and N. Pahlevanyan 2 3

W e d e ¯ n e a r a n d o m p a r t it io n o f T NQ1 ( E ) in t o jMj b in s . Th e e n c o d e r in d e p e n d e n t ly a s s ig n s
a h e lp e r la b e l ( in d e x o f t h e b in ) m 2 f 1 ; 2 ; :::jMjg t o e a c h s e qu e n c e x wit h t h e p r o b a b ilit y

P r fM ( x ) = mg = 1 =jMj:

Th e n we d e ¯ n e a s e c o n d r a n d o m p a r t it io n o ve r T NQ1 ( E ) wit h jSj b in s , a n d t h e e n c o d e r a s s ig n s
a r a n d o m la b e l ( b in -in d e x o f t h is s e c o n d p a r t it io n ) s 2 f 1 ; 2 ; :::jSjg t o e a c h s e qu e n c e x wit h
t h e p r o b a b ilit y

P r fS ( x ) = sg = 1 =jSj:
Th e e n c o d e r e xp lo r e s t h e s e qu e n c e x a n d d e t e r m in e s t h e s e c r e t la b e l s a n d h e lp e r la b e l m.
Th e e n c o d e r s e n d s t h e h e lp e r la b e l m t o t h e d e c o d e r .
Th e d e c o d e r a ft e r h a vin g o b s e r ve d y s e qu e n c e lo o ks fo r a u n iqu e s e qu e n c e x wit h t h e h e lp e r
la b e l m s u c h t h a t ( x; y ) 2 TP ( X; Y ) a n d D ( P jjQ ) is m in im a l.

E r r or pr obability. Fr o m ( 3 ) we o b t a in t h a t fo r a n y P s u c h t h a t D ( P jjQ ) > E t h e
p r o b a b ilit y o f t h e e ve n t is s m a ll e n o u g h

QN ( T NP ( X; Y ) ) · e xp f¡NEg: ( 8 )

Th e d e c o d e r c a n m a ke a n e r r o r if fo r t h e g ive n m t h e s e c r e t s wa s d e t e r m in e d , b u t t h e r e
e xis t s ŝ 6= s, s u c h t h a t fo r s o m e P̂

( xm ( s) ; ym ) 2 TP ( X; Y ) ; ( x̂m ( ŝ) ; ym ) 2 TP̂ ( X; Y )

a n d
D ( P̂ jjQ ) · D ( P jjQ) :

Th e m a t h e m a t ic a l e xp e c t a t io n o f t h is e ve n t c a n b e u p p e r b o u n d e d b y t h e fo llo win g e xp r e s -
s io n : X

P;P̂ :D(P̂ jjQ)·D(P jjQ)

X

ŝ6=s

X

x2X N

X

y2YN
Q N ( x; y ) £

P r f ( xm ( s) ; ym ) 2 T NP ( X; Y ) g £ P r f ( x̂m ( ŝ) ; ym ) 2 T NP̂ ( X; Y ) g:
Th e ¯ r s t p r o b a b ilit y is d i®e r e n t fr o m z e r o o n ly if x 2 T NP1 ( X ) a n d y 2 T

N
P ( Y ) : H e n c e , t h e

e xp r e s s io n will h a ve t h e fo llo win g fo r m :

X

P;P̂ :D(P̂ jjQ)·D(P jjQ)

X

ŝ6=s

X

x2T N
P1

(X)

X

y2T N
P

(Y )

Q N ( x; y ) £

P r f ( xm ( s) ; ym ) 2 T NP ( X; Y ) g £ P r f ( x̂m ( ŝ) ; ym ) 2 T NP̂ ( X; Y ) g:
Ta kin g in t o a c c o u n t t h a t fo r a n y P̂

jSj ¡ 1 · e xp fN ( IP̂ ( X ^ Y ) + D ( P̂ jjQ ) ¡ E ¡ ±1 ) g

a n d ( 1 ) , ( 2 ) t h e la s t e xp r e s s io n will n o t b e g r e a t e r t h a n

X

P;P̂ :D(P̂ jjQ)·D(P jjQ)
e xp fN ( IP̂ ( X ^ Y ) + D ( P̂ jjQ) ¡ E ¡ ±1 ) g£

e xp f¡N ( HP ( X; Y ) + D ( P jjQ ) ) g £ e xp fN ( HP ( X ) + HP ( Y ) ) g£



2 4 Information Theoretical Analysis of Biometric Generated Secret Key Sharing Model

e xp f¡N ( IP ( X ^ Y ) ¡ ±2 ) g £ e xp f¡N ( IP̂ ( X ^ Y ) ¡ ±3 ) g =
X

P;P̂ :D(P̂ jjQ)·D(P jjQ)
e xp fN ( D ( P̂ jjQ ) ¡ E ¡ ( ±1 + ±2 + ±3 ) ) g£

e xp f¡ND ( P jjQ ) g · e xp f¡N ( E ¡ ±0 ) g: ( 9 )
Th e n fr o m ( 8 ) a n d ( 9 ) we s t a t e t h a t fo r N la r g e e n o u g h t h e r e e xis t s a c o d e wit h la b e lin g s
M a n d S s u c h t h a t

P r fS 6= Ŝg · e xp f¡N ( E ¡ ±0 ) g + e xp f¡NE ) g · e xp f¡N ( E ¡ ± ) g:
Fo r t h e r e s t o f t h e p r o o f we s t a t e t h a t s in c e P r fS 6= Ŝg · e xp f¡N ( E ¡ ± ) g fo r N la r g e
e n o u g h , t h e r e e xis t s a t le a s t o n e p a ir o f la b e lin g s M; S; s u c h t h a t

H ( M ) · lo g jMj = N m a x
P :D(P jjQ)·E

( HP ( XjY ) ¡ D ( P jjQ ) + E + ²1 ) : ( 1 0 )

H ( S ) · lo g jSj = N m in
P :D(P jjQ)·E

( IP ( X ^ Y ) + D ( P jjQ) ¡ E ¡ ²2 ) : ( 1 1 )

Unifor mity. L e t X̂N b e t h e e s t im a t e o f X N b a s e d o n S a n d M; t h e n we ¯ n d t h a t

H ( X N ) = H ( X N ; S; M ) = H ( S ) + H ( MjS ) +
H ( XN jS; M ) · H ( S ) + H ( M ) + H ( XN jS; M; X̂ N ) ·

H ( S ) + H ( M ) + NPe lo g jX j + 1 ;
t h e la s t s t e p fo llo ws fr o m Fa n o 's in e qu a lit y. H e n c e , fr o m ( 1 0 ) a n d ( 1 1 ) we h a ve

H ( S ) ¸ H ( XN ) ¡ H ( M ) ¡ N Pe lo g jX j ¡ 1 ¸
NH ( X ) ¡ N m a x

P :D(P jjQ)·E
( HP ( XjY ) ¡ D ( P jjQ ) + E + ² ) ¡

N e xp f¡N ( E ¡ ± ) g lo g jX j ¡ 1 ¸
lo g jSj ¡ N ( ²1 ¡ ²2 ) ¡ N e xp f¡N ( E ¡ ± ) g lo g jX j ¡ 1 :

Secr ecy. N o w we s t u d y t h e s e c r e c y.

I ( S ^ M ) = H ( S ) + H ( M ) + H ( S; M ) =
H ( S ) + H ( M ) ¡ H ( S; M; X N ) + H ( XN jS; M ) =
H ( S ) + H ( M ) ¡ H ( XN ) + H ( XN jS; M; X̂ N ) ·

H ( S ) + H ( M ) ¡ N H ( X ) + N P1 lo g jX j + 1 :
Fr o m ( 1 0 ) a n d ( 1 1 ) we o b t a in

H ( S ) + H ( M ) ¡ NH ( X ) + NP1 lo g jX j + 1 ·
N ( m in

P :D(P jjQ)·E
IP ( X ^ Y ) + m a x

P :D(P jjQ)·E
HP ( XjY ) ¡ H ( X ) ) +

N ( ²1 ¡ ²2 ) + N e xp f¡N ( E ¡ ± ) g lo g jX j + 1 :
Fin a lly, we s e e t h a t t h e s e c r e c y le a ka g e is s m a ll fo r N la r g e e n o u g h

1

N
I ( S ^ M ) · e xp f¡N ( E ¡ ± ) g lo g jX j + ( ²1 ¡ ²2 ) +

1

N
:

Th e t h e o r e m is p r o ve d .



M. Haroutunian and N. Pahlevanyan 2 5

6 . P r iva c y L e a ka g e

Th e fo llo win g p r o p o s it io n g ive s t h e p r iva c y le a ka g e c o r r e s p o n d in g t o t h e m a xim u m E-
a c h ie va b le s e c r e t ke y r a t e in t h e b io m e t r ic g e n e r a t e d s e c r e t ke y s h a r in g m o d e l.

P r oposition: In a biometric generated secret key sharing model for E-achievable secret
key rate the privacy leakage is

1

N
IQ1 ( M ^ X N ) = m a x

P :D(P jjQ)·E
( HP ( XjY ) + D ( P jjQ ) ¡ E ) : ( 1 2 )

P r oof: A s M is a fu n c t io n o f X N we h a ve fr o m ( 1 1 )

I ( X N ^ M ) = H ( M ) ¸ H ( XN ) ¡ H ( S ) ¡ NPe lo g jX j ¡ 1 ¸

NHQ1 ( X ) ¡ N m in
P :D(P jjQ)·E

( IP ( X ^ Y ) + D ( P jjQ ) ¡ E ¡ ²2 ) ¡

N 2 ¡N (E¡±) lo g jX j ¡ 1 ¸
N m a x

P :D(P jjQ)·E
( HP ( XjY ) + D ( P jjQ) ¡ E ¡ ²2 ) ¡

N 2 ¡N(E¡±) lo g jX j ¡ 1 :
On t h e o t h e r h a n d fr o m ( 1 0 )

H ( M ) · N m a x
P :D(P jjQ)·E

( HP ( XjY ) ¡ D ( P jjQ) + E + ²1 ) :

D ivid in g b o t h s id e s b y N , a n d fo r N ! 1 we o b t a in ( 1 2 ) .

Remar k: The above proposition gives the privacy leakage if we apply the coding scheme
outlined in the achievability proof. However, it may be possible to achieve a smaller privacy
leakage depending on the secret-key rate. This problem will be considered in the future work.

7 . Co n c lu s io n

W e s t u d ie d t h e b io m e t r ic g e n e r a t e d -s e c r e t m o d e l fo r d is c r e t e i.i.d b io m e t r ic s o u r c e s . Th e
n e w c o n c e p t o f E-a c h ie va b le s e c r e t ke y r a t e is in t r o d u c e d a n d t h e e xp r e s s io n s fo r t h e lo we r
a n d u p p e r b o u n d s o f la r g e s t r a t e a r e o b t a in e d . Th is n o t io n is t h e g e n e r a liz a t io n o f t h e
a c h ie va b le s e c r e t ke y r a t e a s it t e n d s t o t h e la s t wh e n E t e n d s t o z e r o . Th e p r o o fs a r e b a s e d
o n t h e s t r o n g t yp ic a lit y. A ls o a n e xp r e s s io n fo r p r iva c y le a ka g e , wh ic h c o r r e s p o n d s t o t h e
la r g e s t E-a c h ie va b le s e c r e t ke y r a t e is o b t a in e d .

Refer ences

[1 ] T. Ig n a t e n ko a n d F. M. W ille m s , \ B io m e t r ic s e c u r it y fr o m a n in fo r m a t io n -t h e o r e t ic a l
p e r s p e c t ive ," F oundations and Trends in Communications and Information Theory,
vo l. 7 , n o . 2 -3 , p p . 1 3 5 { 3 1 6 , 2 0 1 2 .

[2 ] J. A . O'S u lliva n a n d N . A . S c h m id , \ L a r g e d e via t io n s p e r fo r m a n c e a n a lys is fo r b io m e t -
r ic s r e c o g n it io n " , P roc. 40th Annual Allerton Conf. on Communication, Control, and
Computing, p p . 1 { 1 0 , Oc t . 2 0 0 2 .



2 6 Information Theoretical Analysis of Biometric Generated Secret Key Sharing Model

[3 ] F. W ille m s , T. K a lke r , J. Go s e lin g a n d J.-P . L in n a r t z , \ On t h e c a p a c it y o f a b io m e t r ic a l
id e n t i¯ c a t io n s ys t e m ," in Information Theory, 2003. P roceedings. IE E E International
Symposium on Information Theory, Y o ko h a m a , Ja p a n , 2 0 0 3 , p . 8 2 .

[4 ] E . H a r o u t u n ia n , \ On b o u n d s fo r E-c a p a c it y o f D MC," IE E E Transactions on Informa-
tion Theory, vo l. 5 3 , n o . 1 1 , p p . 4 2 1 0 { 4 2 2 0 , 2 0 0 7 .

[5 ] M. H a r o u t u n ia n , A . Mu r a d ya n a n d L . Te r -V a r d a n ya n , \ U p p e r a n d lo we r b o u n d s o f
b io m e t r ic id e n t ī c a t io n E-c a p a c it y, " Transactions of IIAP of NAS of R A, M athematical
P roblems of Computer Science, vo l. 3 6 , p p . 1 { 1 0 , 2 0 1 2 .

[6 ] M. H a r o u t u n ia n a n d L . Te r -V a r d a n ya n , \ In ve s t ig a t io n o f E-c a p a c it y fo r b io m e t r ic id e n -
t i¯ c a t io n p r o t o c o l wit h r a n d o m p a r a m e t e r ," Transactions of IIAP of NAS of R A, M ath-
ematical P roblems of Computer Science, vo l. 3 9 , p p . 8 8 { 9 3 , 2 0 1 3 .

[7 ] U . Ma u r e r , \ S e c r e t ke y a g r e e m e n t b y p u b lic d is c u s s io n fr o m c o m m o n in fo r m a t io n ,"
IE E E Transactions on Information Theory, vo l. 3 9 , n o . 3 , p p . 7 3 3 { 7 4 2 , Ma y 1 9 9 3 .

[8 ] R . A h ls we d e a n d I. Cs is z a r , \ Co m m o n r a n d o m n e s s in in fo r m a t io n t h e o r y a n d c r yp t o g -
r a p h y. I s e c r e t s h a r in g ," IE E E Transactions on Information Theory, vo l. 3 9 , n o . 4 , p p .
1 1 2 1 { 1 1 3 2 , 1 9 9 3 .

[9 ] Y . Ch e n a n d A . H . V in c k, \ Fr o m p a s s wo r d t o b io m e t r ic s : H o w fa r c a n we g o ," P roceid-
ings 7th Asia-E urope W orkshop on Concepts in Information theory, B o p p a r d , Ge r m a n y,
p p . 1 { 8 , 2 0 1 1 .

[1 0 ] 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 . 2 -3 , p p . 9 7 { 2 6 3 , 2 0 0 8 .

[1 1 ] I. Cs is z a r , \ Th e m e t h o d o f t yp e s ," IE E E Transactions on Information Theory, vo l. 4 4 ,
n o . 6 , p p . 2 5 0 5 { 2 5 2 3 , 1 9 9 8 .

[1 2 ] T. M. Co ve r a n d J. A . Th o m a s , E lements of Information Theory, 2nd E dition, N e w
Y o r k, W ile y-In t e r s c ie n c e , 2 0 0 6 .

Submitted 15.08.2014, accepted 22.11.2014.

¶»Ý»ñ³óí³Í ·³ÕïÝÇ µ³Ý³ÉÇ ÷á˳ݳÏáÕ Ï»Ýë³ã³÷³Ï³Ý
Ùá¹»ÉÇ ÇÝýáñÙ³óÇáÝ-ï»ë³Ï³Ý ѻﳽáïáõÃÛáõÝ

Ø. гñáõÃÛáõÝÛ³Ý ¨ Ü. ö³Ñɨ³ÝÛ³Ý

²Ù÷á÷áõÙ

лﳽáïíáõÙ ¿ ·»Ý»ñ³óí³Í ·³ÕïÝÇ µ³Ý³ÉÇ ÷á˳ݳÏáÕ Ï»Ýë³ã³÷³Ï³Ý
ѳٳϳñ·Á: Ü»ñÙáõÍí»É ¿ ·³ÕïÝÇùÇ E ѳë³Ý»ÉÇ ³ñ³·áõÃÛáõÝ Ýáñ ѳëϳóáõÃÛáõÝÁ,
áñÝ ÁݹѳÝñ³óÝáõÙ ¿ Ʒݳï»ÝÏáÛÇ ¨ ìÇÉ»ÙëÇ [1] áõëáõÙݳëÇñ³Í ·³ÕïÝÇùÇ Ñ³ë³Ý»ÉÇ
³ñ³·áõÃÛ³Ý ·³Õ³÷³ñÁ: γéáõóí»É »Ý ·³ÕïÝÇùÇ E ѳë³Ý»ÉÇ ³é³í»É³·áõÛÝ
³ñ³·áõÃÛ³Ý í»ñÇÝ ¨ ëïáñÇÝ ·Ý³Ñ³ï³Ï³ÝÝ»ñÁ: ºñµ E ! 0 , ëï³óí³Í
·Ý³Ñ³ï³Ï³ÝÝ»ñÇ ë³ÑÙ³ÝÝ»ñÁ ѳÙÁÝÏÝáõÙ »Ý ¨ ѳí³ë³ñ »Ý [1]-áõÙ ëï³ó³Í ·³ÕïÝÇ
µ³Ý³Éáõѳë³Ý»ÉÇ ³ñ³·áõÃÛ³Ý Ù»Í³·áõÛÝ ³ñÅ»ùÇÝ:



M. Haroutunian and N. Pahlevanyan 2 7

Èíôîðìàöèîííî-òåîðåòè÷åñêèé àíàëèç áèîìåòðè÷åñêîé
ìîäåëè ðàñïðåäåëåíèÿ ñãåíåðèðîâàííîãî

ñåêðåòíîãî êëþ÷à
Ì. Àðóòþíÿí è Í. Ïàéëåâàíÿí

Àííîòàöèÿ

Ðàññìàòðèâàåòñÿ áèîìåòðè÷åñêàÿ ñèñòåìà ðàñïðåäåëåíèÿ ñãåíåðèðîâàííîãî
ñåêðåòíîãî êëþ÷à. Ââîäèòñÿ íîâîå ïîíÿòèå E-äîñòèæèìîé ñêîðîñòè ñåêðåòà,
êîòîðîå ÿâëÿåòñÿ îáîáùåíèåì äîñòèæèìîé ñêîðîñòè ñåêðåòà, èçó÷åííîé
Èãíàòåíêî è Âèëåìñîì â [1]. Ïîñòðîåíû âåðõíÿÿ è íèæíÿÿãðàíèöûíàèáîëüøåé
E-äîñòèæèìîé ñêîðîñòè ñåêðåòà. Êîãäà E ! 0 , ïðåäåëûïîëó÷åííûõ ãðàíèö
ñîâïàäàþò ñ íàèáîëüøåé äîñòèæèìîé ñêîðîñòüþ ñåêðåòíîãî êëþ÷à, ïîëó÷åííîé
â [1].