Tìm hiểu và nghiên cứu các đảm bảo xác thực thay cho đảm bảo mật phần 4 pps

Vietebooks Nguyễn Hoàng Cương

Trang 16

§Æc tr−ng sau ®©y cã khã h¬n mét chót chóng ta chØ ph¸t biÓu mµ

kh«ng chøng minh .

§Þnh lÝ 10.2

Gi¶ sö (S,A,K,E) lµ mét m· x¸c thùc ,trong ®ã ⏐A⏐=n vµ

Pd0=Pd1=1/n.Khi ®ã ⏐K⏐≥k(n-1)+1.H¬n n÷a ⏐K⏐=k(n-1)+1 khi vµ

chØ khi cã mét m¶ng trùc giao 0A(n,k,λ),ë ®©y ⏐S⏐=k,λ=(k(n-1)+1)/n2

vµ pK(K)=1/(k(n-1)+1) víi mäi kho¸ K∈K.

NhËn xÐt.Chó ý r»ng ®Þnh lÝ 10.10 t¹o ra mét líp v« h¹n c¸c m¶ng trùc

giao ®¹t ®−îc giíi h¹n ë ®Þnh lÝ 10.12 víi dÊu “=”.

10.4.c¸c giíi h¹n entropy

Trong phÇn nµy chóng ta dïng kÜ thuËt entropy ®Ó nhËn ®−îc c¸c

giíi h¹n vÒ c¸c x¸c suÊt lõa bÞp .Tr−íc tiªn ta sÏ xÐt c¸c giíi h¹n ®èi

víi Pd0.

§Þnh lÝ 10.13

Gi¶ sö (S,R.K,E) lµ mét m· x¸c thùc .Khi ®ã

LogPd0≥H(K⏐M)-H(K)

Chøng minh:

Tõ ph−¬ng tr×nh (10.1) ta cã :

Pd0≥ max{payoff(s,a):s∈S,a∈R}

V× gi¸ trÞ cùc cña payoff(s,a) ph¶i lín h¬n trung b×nh c¸c träng sè cña

chóng nªn ta nhËn ®−îc:

Pd0≥∑s∈S,a∈RpM(s,a)payoff(s,a)

Nh− vËy thoe bÊt ®¼ng thøc Jensen(dÞnh lÝ (2.5) ta cã :

LogPd0≥log∑s∈S,a∈RpM(s,a)payoff(s,a)

≥∑s∈S,a∈RpM(s,a)log payoff(s,a)

Theo phÇn 10.2:

PM(s,a)=ps(s)x payoff(s,a)

Ta thÊy r»ng:

Log Pd0≥∑s∈S,a∈Rps(s)payoff(s,a) log payoff(s,a)

B©y giê ta thÊy r»ng payoff(s,a)=pR(a⏐s)(tøc lµ x¸c suÊt ®Ó a lµ nh·n

x¸c thùc víi ®iÒu kiÖn s lµ tr¹ng th¸i nguån ).Bëi vËy:

LogPd0 ≥ ∑s∈S,a∈Rps(s).pR(a⏐s) logpR(a⏐s) =-H(A⏐S)