Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 2

Tất cả các tính toán của Vic có thể thực hiện được trong thời gian đa thức (như một hàm của n là số các đỉnh trong G1 và G2).
Nội dung trích xuất từ tài liệu:
Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 2Vietebooks Nguyễn Hoàng Cươngmçi vßng vµ ghi mét b¶n sao ®¼ng cÊu (ngÉu nhiªn ) cña G1 lªn b¨ng liªn l¹c.X¸c suÊt ®Ó Peggy gi¶ ®Þnh ®óng c¸c yªu cÇu cña Vic lµ 2n.?????????????????????????????? TÊt c¶ c¸c tÝnh to¸n cña Vic cã thÓ thùc hiÖn ®−îc trong thêi gian ®athøc (nh− mét hµm cña n lµ sè c¸c ®Ønh trong G1 vµ G2). MÆc dï kh«ng cÇnthiÕt l¾m nh−ng ta còng thÊy r»ng c¸c tÝnh to¸n cña Peggy còng cã thÓ ®−îcthùc hiÖn trong thêi gian ®a thøc miÔn lµ c« ta biÕt ®−îc sù tån t¹I cña phÐpho¸n vÞ δ lµ G1. T¹i sao ta l¹i coi hÖ thèng chøng minh lµ hÖ th«ng chøng minh kh«ngtiÕt lé th«ng tin. Lý do lµ ë chç mÆc dï Vic ®· bÞ thuyÕt phôc r»ng G1 lµ ®¼ngcÊu víi G2 nh−ng anh ta vÉn kh«ng thu thªm ®−îc tý kiÕn thøc nµo ®Ó giópt×m ®−îc phÐp ho¸n vÞ δ ®−a G2 vÒ G1. TÊt c¶ nh÷ng ®IÒu mµ Vic thÊy trongmçi vßng cña phÐp chøng minh lµ mét b¶n sao ngÉu nhiªn cña c¸c ®é thÞ nµymµ kh«ng cÇn tíi sù gióp ®ì cña Peggy. V× c¸c ®å thÞ H ®−îc chän mét c¸ch®éc lËp vµ ngÉy nhiªn ë mçi phÇn cña phÐp chøng minh nªn ®IÒu nµy kh«nggióp ®ì ®−îc g× vho Vic trong viÖc t×m mét phÐp d¼ng cÊu tõ G1 sang G2. Ta h·y xem xÐt kÜ l−ìng th«ng tin mµ Vic thu ®−îc nhê tham gia vµohÖ th«ng chøng minh t−¬ng hç. Cã thÓ biÓu thÞ c¸ch nh×nh cña Vic vÒ phÐpchøng minh t−¬ng b»ng mét “ b¶n sao ” chøa c¸c th«ng tin sau:____ 1.C¸c ®å thÞ G1 vµ G2 2. TÊt c¶ c¸c th«ng b¸o ®−îc Peggy vµ Vic göi ®i. 3. C¸c sè ngÉu nhiªn mµ Vic dïng ®Ó tµo c¸c yªu cÇu cña m×nh.Bëi vËy mét b¶n sao T ®èi víi phÐp chøng minh t−¬ng hç vÒ phÐp ®¼ng cÊu®å thÞ sÏ cã d¹ng sau: T = ((G1, G2):(H1, i1, p1): . . . (Hn, in, pn))§iÓm mÊu chèt (t¹o c¬ së cho ®Þnh nghÜa h×nh thøc vÒ phÐp chøng minhkh«ng tiÕt lé th«ng tin ) lµ Vic (hay vÊt kú ng−êi nµo kh¸c) cã thÓ gi¶ m¹o Trang 6Vietebooks Nguyễn Hoàng Cươngc¸c b¶n sao (mµ kh«ng cÇn ph¶i tham gia vµo hÖ chøng minh t−¬ng hç)”gièng nh−” c¸c b¶n sao thùc tÕ. §iÒu nµy cã thÓ thùc hiÖn ®−îc miÔn lµ c¸c®å thÞ G1 vµ G2 lµ ®¼ng cÊu. ViÖc gi¶ m¹o ®−îc thùc hiÖn theo thuËt to¸n m«t¶ trªn h×nh 13.6. thuËt to¸n gi¶ m¹o lµ mét thuËt to¸n x¸c suÊt theo thêi gian®· thøc. Theo nh«n ng÷ cña phÐp chøng minh kh«ng tiÕt lé th«ng tin métthuËt to¸n gi¶ m¹o th−êng ®−îc gäi lµ mét bé m« pháng. Sù kiÖn mét bé m« pháng cã thÓ gi¶ m¹o c¸c b¶n sao cã mét hÖ qu¶ rÊtquan träng. BÊt kú kÕt qu¶ nµo mµ Vic (hay bÊt k× ai kh¸c ) cã thÓ tÝnh tõ métb¶n sao còng cã thÓ tÝnh ®−îc tõ mét b¶n sao gi¶ m¹o. Bëi vËy ,viÖc tham giavµo hÖ th«ng chøng minh sÏ kh«ng lµm t¨ng kh¶ n¨ng tÝnh to¸n cña Vic; ®ÆcbiÖt lµ ®iÒu nµy kh«ng cho phÐp Vic tù chøng minh ®−îc r»ng G1 vµ G2 lµ®¼ng cÊu. H¬n n÷a, Vic còng kh«ng thÓ thuyÕt phôc ®−îc ai kh¸c r»ng G1vµG2 lµ ®¼ng cÊu b»ng c¸ch chØ cho hä b¶n soa T bëi v× kh«ng cã c¸ch nµo ®Óph©n biÖt mét b¶n sao hîp lÖ víi mét b¶n sao gi¶ m¹o. Ta sÏ chÝnh x¸c ho¸ ý t−ëng vÒ mét b¶n sao gi¶ m¹o “gièng nh−” mét b¶nsao thùc vµ ®−a ra mét ®Þnh nghÜa chÆt chÏ theo thuËt ng÷ vÒ c¸c ph©n bè x¸csuÊt.§Þnh nghÜa 13.1 Gi¶ sö ta cã mét chøng minh t−¬ng hç thêi gian ®a thøc cho b¸i to¸nquyÕt ®Þnh ∏ vµ mét bé m« pháng thêi gian ®a thøc S. KÝ hiÖu tËp tÊt c¶ c¸cb¶n sao cã thÓ cho kÕt qu¶ cã x lµ F(x). C¸c b¶n sao gi¶ m¹o cã thÓ ®−îc t¹obëi S lµ F(x). víi b¶n sao bÊt kú T∈ τ ( x) ,cho b¶n sao gi¶ m¹o cã thÓ ®−îc t¹obëi S lµ F(x). víi b¶n sao bÊt k× T ∈ τ ( x) cho p τ (T) lµ x¸c suÊt ®Ó T lµ métb¶n sao ®−îc t¹o tõ phÐp chøng minh t−¬ng hç. T−¬ong tù, víi T∈ F(x), chop τ (T) lµ x¸c suÊt ®Ó T lµ mét b¶n sao (gi¶ m¹o) ®−îc t¹o bëi S, Gi¶ sö r»ngτ ( x) = F ( x) vµ víi bÊt kú T∈ τ ( x) ta cã p τ (T) = pF(T) (nãi c¸ch kh¸c tËp c¸cb¶n sao thùc ®ång nhÊt víi tËp c¸c b¶n sao gi¶ m¹o vµ hai ph©n bè x¸c suÊtlµ nh− nhau). Khi ®ã ta ®Þnh nghÜa hÖ thèng chøng minh t−¬ng hç lµ hÖ th«ngchøng minh kh«ng tiÕt lé thiing tin hoµn thiÖn ®èi víi Vic.H×nh 13.6 thuËt to¸n gi¶ m¹o cho c¸c b¶n sao ®èi víi phÐp ®¼ng cÊu ®å thÞ Trang 7Vietebooks Nguyễn Hoàng Cương §Çu vµo : hai ®å thÞ G1 vµ G2 mçi ®å thÞ cã tËp ®Ønh {1...n} 1. T=(G1, G2) 2. For j=1 to n do 3. Chän ngÉu nhiªn ij=1 hoÆc 2; 4. Chän pj lµ mét ho¸n vÞ ngÉu nhiªn cña{1...n} 5. TÝnh Hj lµ ¶nh cña G1 theo pj 6. GhÐp (Hj, ij, pj) vµo cuèi cña T DÜ nhiªn lµ cã thÓ ®Þnh nghÜa ®Æc tÝnh kh«ng tiÕt lé th«ng tin theo kiÓumµ ta thiÐc. Tuy nhiªn ®iÒu quan träng lµ ®Þnh nghÜa ph¶i gi÷ néi dung c¬b¶n cña ®Æc tÝnh nµy. Ta ®· coi r»ng mét hÖ thèng chøng minh t−¬ng hç lµ hÖkh«ng tiÕt lé th«ng tin cho Vic nÕu tån t¹i mét hÖ m« pháng r¹o ra c¸c b¶nsao cã ph©n bè x¸c suÊt ®ång nhÊt víi ph©n bè x¸c suÊt cña c¸c b¶n ...