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

Các chứng minh không tiết lộ thông tin 13.1.các hệ thống chứng minh tương hỗ Một cách đơn giản, một hệ thống chứng minh không tiết lộ thông tin sẽ cho phép một đối tượng thuyết phục được một đối tượng khác tin một điều nào đó mà không để lộ một tý thông tin nào về phép chứng minh.
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 1Vietebooks Nguyễn Hoàng CươngGiáo trình tin học: Hướng dẫn cácCh−¬ng 13 không cần tiết lộ thông tin chứng minh mà C¸c chøng minh kh«ng tiÕt lé th«ng tin13.1.c¸c hÖ thèng chøng minh t−¬ng hç Mét c¸ch ®¬n gi¶n, mét hÖ thèng chøng minh kh«ng tiÕt lé th«ng tin sÏcho phÐp mét ®èi t−îng thuyÕt phôc ®−îc mét ®èi t−îng kh¸c tin mét ®iÒunµo ®ã mµ kh«ng ®Ó lé mét tý th«ng tin nµo vÒ phÐp chøng minh. Tr−íc tiªnta sÏ th¶o luËn ý t−ëng vÒ mét hÖ thèng chøng minh t−¬ng hç. Trong mét hÖthèng chøng minh t−¬ng hç cã hai thµnh viªn: teggy vµ Vic. Teggy lµ ng−êichøng minh vµ Vic lµ ng−êi kiÓm tra. Teggy biÕt mét ®iÒu g× ®ã vµ c« tamuèn chøng minh cho Vic r»ng c« ta biÕt ®iÒu ®ã. §iÒu cÇn thiÕt lµ ph¶i m« t¶ ®−îc c¸c kiÓu tÝnh to¸n mµ Peggy vµ Vic®−îc phÐp thùc hiÖn vµ c¸c t¸c ®éng qua l¹i x¶y ra. Ta cã thÓ coi c¸c thuËtto¸n mµ Peggy vµ Vic thùc hiÖn lµ c¸c thuËt to¸n x¸c suÊt. Peggy vµ Vic sÏthùc hiÖn c¸c tÝnh to¸n riªng vµ mçi ng−êi ®Òu cã mét bé t¹o sè ngÉu nhiªnriªng. Hä sÏ liªn l¹c víi nhau qua mét kªnh truyÒn tin. Tho¹t ®Çu c¶ Peggy vµVic ®Òu cã mét gi¸ trÞ x. môc ®Ých cña phÐp chøng minh t−¬ng hç lµ Peggyph¶I thuyÕt Vic r»ng x cã mét tÝnh chÊt x¸c ®×nh nµo ®ã. ChÝnh x¸c h¬n x lµc©u tr¶ lêi cã cña mét b¸i to¸n quyÕt ®Þnh x¸c ®Þnh ∏. PhÐp chøng minh t−¬ng hç (lµ mét giao thøc hái-®¸p) gåm mét sèvßng x¸c ®Þnh. Trong mçi vßng .Peggy vµ Vic lu©n phiªn thùc hiÖn c¸c c«ngviÖc sau: 1. NhËn mét th«ng b¸o tõ nhãm kh¸c . 2.Thùc hiÖn mét tÝnh to¸n riªng. 3. Göi mét th«ng b¸o toi− nhãm kh¸c Mét vßng ®IÓn h×nh cña giao thøc sÏ gåm mét yªu cÇu cña Vic vµ mét®¸p øng cña Peggy. Tíi cuèi phÐp chøng minh ,Vic hoÆc sÏ chÊp nhËn hoÆctõ chèi tuú thuéc vµo viÖc liÖu Peggy cã ®¸p øng thµnh c«ng c¸c yªu c©ï cñaVic hay kh«ng. Ta ®Þnh nghÜa giao thøc lµ mét hÖ th«ng chøng minh t−¬nghç ®èi víi v¸i to¸n quyÕt ®Þnh ∏ nÕu hai tÝnh chÊt sau ®−îc tho¶ m·n mçi khiVic tu©n theo giao thøc ®ã:TÝnh ®Çy ®ñ Trang 1Vietebooks Nguyễn Hoàng Cương NÕu x lµ c©u tr¶ lêi cã cña hai b¸i to¸n quyÕt ®Þnh ∏ th× Vic sÏ lu«n lu«nchÊp nhËn chøng minh cña Peggy.TÝnh ®óng ®¾n NÕu x lµ c©u tr¶ lêi kh«ng cña ∏ th× x¸c suÊt ®Ó Vic chÊp nhËn phÐpchøng minh lµ rÊt nhá. Ta h¹n chÕt chØ xÐt c¸c hÖ thèng chøng minh t−¬ng hç mµ c¸c tÝnhto¸n do Vic thøc hiÖn n»m trong tho× gian ®a thøc song kh«ng hµn chÕ thêigian tÝnh to¸n mµ prggy thùc hiªn.(Peggy ®−îc coi lµ “toµn n¨ng”). Ta sÏ b¾t ®Çu b»ng viÖc tr×nh bµy mét hÖ thèng chøng minh t−¬ng hçcho b¸i to¸n ®å thÞ kh«ng d¼ng cÊu. B¸i to¸n ®¼ng cÈu ®å thÞ ®−îc m« t¶ trªnh×nh 13.1. §©y lµ mét b¸i to¸n thó vÞ mµ cho tíi nay ng−êi ta ch−a biÕt thuËtgi¶i nµo cã thêi gian ®a thøc tuy r»ng kh«ng ®−îc coi lµ b¸i to¸n NP ®Çy ®ñ.H×nh 13.1 . tÝnh ®¼ng cÊu ®å thÞ §Æc tr−ng cña b¸i to¸n : 2 ®å thÞ n ®Ønh G1=(V1,E1) vµ G2=(V2,E2) C©u hái: liÖu cã mét song ¸nh π: V1 V2 sao cho {u,v}∈E1 khi vµ chØ khi {π(u), π(v)} ∈ E2 kh«ng ?. (nãi c¸ch kh¸c liÖu G1 vµ G2 cã ®¼ng cÊu kh«ng ?) Sau ®©y sÏ tr×nh bµy mét hÖ thèng chøng minh t−¬ng hç cho phÐp Peggychøng tá víi Vic r»ng 2 ®å thÞ chØ ra lµ kh«ng ®¼ng cÊu. §Ó ®¬n gi¶n, gi¶ sör»ng mçi ®å thÞ G1 vµ G2 cã tËp ®Ønh {1..n}. HÖ th«ng chøng minh t−¬ng hç®èi víi tÝnh kh«ng ®¼ng cÊu ®å thÞ ®−îc m« t¶ trªn h×nh 13.2. Trang 2Vietebooks Nguyễn Hoàng CươngH×nh 13.2. Mét hÖ thèng chøng minh t−¬ng hç ®èi víi tÝnh kh«ng ®¼ngcÊu ®å thÞ §Çu vµo :mçi ®å thÞ G1 vµ G2 cã tËp ®Ønh {1,....,n} 1. H·y lÆp l¹i c¸c b−íc sau n lÇn: 2. Vic chän mét sè ngÉu nhiªn I=1 hoÆc 2 vµ mét phÐp ho¸n vÞ ngÉu nhiªn π cña {1,...,m}.Vic sÏ tÝnh H lµ ¶nh cña G theo ho¸n vÞ π vµ göi H cho Peggy. 3. Peggy x¸c ®Þnh gi¸ trÞ j sao cho Gj lµ ®¼ng cÊu víi H vµ göi j cho Vic 4. Vic sÏ kiÓm tra xem liÖu i=j kh«ng . 5. Vic chÊp nhËn chøng minh cña Peggy nÕu I=j trong mçi vßng.H×nh 13.3 c¸c ®å thÞ kh«ng ®¼ng cÊu cña Peggy vµ yªu cÇu cña Vic????????????????????? VÝ dô nhá sau ®©y sÏ minh ho¹ cho ho¹t ®éng cña thuËt to¸nVÝ dô 13.1 Trang 3Vietebooks Nguyễn Hoàng Cương Gi¶ sö G1 = (V, E1)vµ G2=(V, E2) trong ®ã V = (1, 2, 3, 4), E1 = {12, 14,23, 34}, E2 ={112,13,14,34}. GØa sö ë mét vßng nµo ®ã cña giao thøc,Vic trao cho Peggy ®å thÞH=(V, E3) trong ®ã E3={13, 14, 23, 24}(xem h×nh 13.3). §å thÞ H lµ ®¼ngcÊu víi G1. (Mét phÐp ®¼ng cÊu tõ H vµo G1 lµ phÐo ho¸n vÞ (1 3 4 2)). BëivËy Peggy sÏ tr¶ lêi “1” DÔ dµng nhËn thÊy r»ng, hÖ thèng chøng minh nµy tho¶ m·n tÝnh ®Çy ®ñvµ tÝnh ®óng ®¾n. NÕu G1 kh«ng ®¼ng cÊu víi G2 th× j sÏ b»ng i ë mçi vßng vµVic sÏ chÊp nhËn víi x¸c suÊt 1. Bëi vËy giao thøc lµ ®Çy ®ñ. MÆt kh¸c, gi¶ sö r»ng G1 ®¼ng cÊu víi G2. Khi ®ã mét ®å thÞ yªu cÇu bÊtkú H ®−îc Vic ®−a ra ®¼ng cÊu víi c¶ G1 vµ G2. Peggy sÏ kh«ng cã c¸ch nµo®Ó x¸c ®Þnh xem H lµ phiªn b¶n ®¼ng cÊu nµo cña G1 hay G2 nªn Peggykh«ng cßn c¸ch nµo kh¸c h¬n lµ ph¶i tr¶ lêi b»ng c¸ch gi¶ ®Þnh j=1 hoÆc 2.C¸ch duy nhÊt ®Ó Vic chÊp nhËn lµ xem Peggy cã kh¶ n¨ng ph¸n ®o¸n tÊt c¶n phÐp chän i do Vic thùc hiÖn hay kh«ng. X¸c suÊt Peggy thùc hiÖn ®iÒu nµylµ 2n. Bëi vËygiao thøc lµ ®óng ®¾n. Chó ý r»ng c¸c tÝnh to¸n cña Vic ®Òu trong thêi gian ®a thøc. Ta kh«ngthÓ nãi tý g× vÒ thêi gian tÝnh to¸n cñ Peggy v× b¸i to¸n ®å thÞ ®¼ng cÊu ch−acã mét thuËt gi¶i nµo theo thêigian ®a thøc. Tuy nhiªn h·y nhí l¹i r»ng ta ®·cho Peggy cã n¨ng lùc tÝnh to¸n kh«ng h¹n chÕ vµ bëi vËy ®Òu nµy ®−îc chÊpnhËn theo “c¸c quy t¾c cña trß ch¬i”.13.2. C¸c ...