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

Đặ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 ,
Nội dung trích xuất từ tài liệu:
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 4Vietebooks 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 16Vietebooks 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 17Vietebooks 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- ...