Đặ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 ,
AMBIENT/
Chủ đề:
Nội dung Text: 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
- Vietebooks Nguyễn Hoàng Cương
§Æ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)
Trang 16
- Vietebooks Nguyễn Hoàng Cương
Theo ®Þnh nghÜa cña entropy cã ®iÒu kiÖn .Ta sÏ hoµn chØnh chøng
minh ®Þnh lÝ b»ng c¸ch chØ ra r»ng: -H(A⏐S)=H(K⏐M)-H(K).§iÒu
kiÖn nµy ®−îc rót ra tõ c¸c ®ång nhÊt thøc c¬ b¶n cña entropy.Mét mÆt
ta cã :
H(K,A,S)=H(A⏐K,S)+H(A⏐S)+H(S)
MÆt kh¸c ta tÝnh:
H(K,A,S)=H(A⏐K,S)+H(K,S)=H(S)+H(K)
Ë ®©y ta cã sö dông ®iÒu kiÖn H(A⏐K,S)=0 v× kho¸ vµ tr¹ng th¸i nguån
sÏ x¸c ®Þnh nh·n x¸c thùc mét c¸ch duy nhÊt .Ta còng dïng ®¼ng thøc
H(A⏐S)=H(K)+H(S) v× nguån vµ kho¸ lµ c¸c biÕn cè ®éc lËp.
So s¸nh hai biÓu thøc biÓu thÞ H(K,S,A) ta cã:
-H(A,S)=H(K⏐A,S)-H(K)
Tuy nhiªn th«ng b¸o m=(s,a) ®−îc x¸c ®Þnh gåm mét tr¹ng th¸i nguån
vµ mét tr¹ng th¸i nh·n x¸c thùc(nghÜa lµ M=SxA).Bëi vËy:
H(K⏐A,S)=H(K⏐M)
§Þnh lÝ ®−îc chøng minh.
Sau ®©y ta sÏ chØ ®−a ra mµ kh«ng chøng minh giíi h¹n t−¬ng tù
cho Pd1.
§Þnh lÝ 10.4
Gi¶ sö r»ng (S,A,K,E) lµ mét m· x¸c thùc .Khi ®ã
LogPd1≥H(K⏐M2)-H(K⏐M)
CÇn ph¶i x¸c ®Þnh giíi h¹n entropy theo biÕn ngÉu nhiªn M2.Gi¶ sö ta
x¸c thùc hai tr¹ng th¸i nguån kh¸c nhau dïng cïng mét kho¸ K.Theo
c¸ch nµy ta nhËn ®−îc mét cÆp ®−îc s¾p c¸c banr tin (m1,m2)∈MxM.§Ó
x¸c ®Þnh ph©n bè x¸c suÊt trªn MxM,cÇn ph¶i x¸c ®Þnh x¸c suÊt trªn
SxS víi ®iÒu kiÖn psxs(s,s)=0 víi mäi s∈S(nghÜa lµ kh«ng cho phÐp lÆp
l¹i tr¹ng th¸i nguån ).C¸c ph©n bè x¸c suÊt trªn K vµ SxS sÏ dÉn ®Õn
ph©n bè x¸c suÊt trªn MxM t−¬ng tù nh− ph©n bè x¸c suÊt trªn K vµ S
sÏ t¹o nªn mét ph©n bè x¸c suÊt trªn M DÓ minh ho¹ cho hai giíi h¹n
trªn ,xÐt cÊu tróc m¶ng trùc giao c¬ b¶n vµ chØ ra r»ng c¶ hai giíi h¹n
trong ®Þnh lÝ 10.13 vµ 10.14 ®Òu ®¹t ®−îc víi dÊu b»ng.Tr−íc hÕt ta dÔ
thÊy r»ng:
H(K)=logλn2
V× mçi mét trong λn2 quy t¾c x¸c thùc ®Òu ®−îc chän ®ång x¸c
suÊt.TiÕp theo ta sÏ quay l¹i viÖc tÝnh to¸n H(K⏐M).Nõu ®· quan s¸t
®−îc mét b¶n tin m=(s,a) nµo ®ã th× ®iÒu nµy sÏ giíi h¹n c¸c khãa sÏ
n»m trong tËp con cã lùc l−îng λn.Mçi kho¸ trong λn khãa nµy sÏ cã
Trang 17
- Vietebooks Nguyễn Hoàng Cương
tËp con nh− nhau .V× thÕ H(K⏐m)=logλn víi b¶n tin n bÊt k× .Khi ®ã ta
cã :
H(K⏐M)=∑m∈MpM(m)H(K⏐m)
=∑∈MpM(m)logλn
=log λn
Nh− vËy ta cã:
H(K⏐M)-H(K)=logλn-logλn2=-logn=logPd0
Nh− vËy giíi h¹n tho¶ m·n víi dÊu “=”.
Nõu ta quan s¸t ®−îc hai b¶n tin (®−îc t¹o ra theo cïng mét kho¸ vµ
c¸c tr¹ng th¸i nguån kh¸c nhau )th× sè c¸c kho¸ cã thÓ gi¶m xuèng cßn
λ.LËp luËn t−¬ng tù nh− trªn ta thÊy r»ng H(K⏐M2)=logλ.Khi ®ã:
H(K⏐M)-H(K)=logλ-logλn
=-logn=-Pd1
Nh− vËy giíi h¹n nµy ®−îc tho¶ m·n víi dÊu “=”.
10.5.c¸c chó gi¶i vµ tµi liÖu dÉn
C¸c m· x¸c thùc ®−îc ph¸t minh vµo n¨m 1974 bëi Gilbert.Mac-
Williams vµ Sloane [GMS 74−.NhiÕu phÇn lÝ thuyÕt vÒ c¸c m· x¸c thùc
®· ®−îc Simones ph¸t triÓn,«ng ®· chøng minh nhiÒu kÕt qu¶ c¬ b¶n
trong lÜnh vùc nµy.Hai bµi tæng quan h÷a Ých cña Simones lµ [Si92] vµ
[Si88].Massey còng tr×nh bµy mét tæng quan kh¸ hay kh¸c trong
[Ma86].C¸c mèi liªn hÖ gi÷a c¸c m¶ng trùc giao vµ c¸c m· x¸c thùc ®·
lµ mèi quan t©m cña nhiÒu nhµ nghiªn cøu..C¸ch tr×nh bµy ë ®©y dùa
vµo ba bµi b¸o cña Stinson[St 88],[St 90]vµ [St 92].C¸c m¶ng trùc giao
®· ®−îc nghiªn cøu trong h¬n 45 n¨m bëi c¸c nhµ nghiªn cøu trong
lÜnh vùc thèng kª vµ trong lÝ thuyÕt thiÕt kÕ tæ hîp.VÝ dô,giíi h¹n trong
®Þnh lÝ 10.9 lÇn ®Çu tiªn ®−îc chøng minh bëi Placket vµ Berman vµo
1945 trong [PB 45].NhiÒu kÕt qu¶ thó vÞ vÒ c¸c m¶ng trùc giao cã thÓ
t×m ®−îc trong nhiÒu gi¸o tr×nh kh¸c nhau vÒ lÝ thuyÕt thiÕt kÕ tæ
hîp(ch¼ng h¹n nh− trong [BJL 8] cña Beth,Jungickel vµ Lenz).
Cuèi cïng viÖc sö dông kÜ thuËt entropy trong viÖc nghiªn cøu c¸c
m· x¸c thùc do Simone ®−a ra .Giíi h¹n cña ®Þnh lÝ 10.13 ®· ®−îc
Simone chøng minh tr−íc tiªn trong [Si 85];mét c¸nh chøng minh cña
®Þnh lÝ 10.14 cã thÓ t×m ®−îc trong [Wa 90] cña Walker.
Trang 18
- Vietebooks Nguyễn Hoàng Cương
BμI TËP
10.1.H·y tÝnh Pd0 vµ Pd1 cña m· x¸c thùc ®−îc biÓu thÞ trong ma trËn
sau :
Kho¸ 1 2 3 4
1 1 1 2 3
2 1 2 3 1
3 2 1 3 1
4 2 3 1 2
5 3 2 1 3
6 3 3 2 1
C¸c ph©n bè x¸c suÊt trªn S vµ K nh− sau:
Ps(1)=ps(4)=1/6 ,ps(2)=ps(3)=1/3
pK(1)=pK(6)=1/4, pK(2)=pK(3)=pK(4)=pK(5)=1/8.
Nªu c¸c chiÕn l−îc thay thÕ vµ gi¶ m¹o tèi −u .
10.2.Ta ®· biÕt cÊu tróc ®èi víi mét m¶ng trùc giao 0A(p,p,1)khi p lµ
sè nguyªn tè.H·y chøng tá r»ng lu«n cã thÓ më réng 0A(p,p,1)thªm
mét cét n÷a ®Ó t¹o thµnh 0A(p,p+1,1).H·y minh h¹o cÊu tróc cña b¹n
trong tr−êng hîp p=5.
10.3.Gi¶ sö A lµ mét cÊu tróc 0A(n1,k,λ1) trªn tËp kÝ hiÖu {1,...,n1} vµ
gi¶ sö B lµ mét 0A(n2,k,λ2) trªn tËp kÝ hiÖu {1,...,n2}Ta x©y dùng C lµ
mét 0A(n1,n2,k,λ1λ2) trªn tËp kÝ hiÖu {1...n1}x{1...n2} nh− sau :víi mçi
hµng r1=(x1...xk) cña A vµ víi mçi hµng s1={y1...yk} cña B ta x¸c ®Þnh
mét hµng t1 cña C lµ:
t1=((x1,y1),...,(xk,yk)).
H·y chøng manh r»ng C thùc sù lµ mét 0A(n1n2,k,λ1λ2).
10.4.H·y x©y dùng mét m¶ng trùc giao 0A(3,13,3).
10.5H·y viÕt mét ch−¬ng tr×nh m¸y tÝnh ®Ó tÝnh H(K),H(K⏐M) vµ
H(K⏐M2)cho m· x¸c thùc ë bµi to¸n 10.1Ph©n bè x¸c suÊt trªn cavcs
d·y cña hai nguån lµ :
p S 2 (1.2) = p S 2 (1.3) = p S 2 (1.4) = 1 / 18
p S 2 (2.1) = p S 2 (2.3) = p S 2 (2.4) = 1 / 9
p S 2 (3.1) = p S 2 (3.2) = p S 2 (3.4) = 1 / 9
p S 2 (4.1) = p S 2 (4.2) = p S 2 (4.3) = 1 / 18
H·y so s¸nh giíi h¹n entropy cña Pd0 vµ Pd1 víi c¸c gi¸ trÞ mµ b¹n tÝnh
®−îc trong bµi tËp 10.1.
ChØ dÉn:§Ó tÝnh pK(k⏐m) h·y dïng c«ng thøc Bayes:
Trang 19
- Vietebooks Nguyễn Hoàng Cương
p M (m k ) p K (k )
pK(k⏐m) =
p M ( m)
Ta ®· biÕt c¸ch tÝnh pM(m).§Ó tÝnh pM(m⏐k) h·y viÕt m=(s,a) vµ
nhËn xÐt thÊy r»ng :pM(m⏐k)=pS(s) nÕu eK(s)=a vµ pM(m⏐k)=0 trong
tr−êng hîp ng−îc l¹i .
Trang 20
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
