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

Chú ý rằng mọi tính toán của Víc là theo thời gian đa thức và tính toán của Peggy cũng vậy ,miễn là cô ta biết được sự tồn tại của một phép tô 3 mầu ф. Sau đây là một ví dụ nhỏ để minh hoạ: Ví dụ 13.3
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 5Vietebooks Nguyễn Hoàng Cương®Þnh mét mÇu lµ mét ho¸n vÞ cña phÐp t« mµu x¸c ®Þnh ф.Vic sÏ yªu cÇuPeggy më c¸c blob øng víi c¸c ®iÓm cuèi cña mét c¹nh nµo ®ã ®−îc chänngÉu nhiªn.Peggy sÏ thùc hiÖn c¸c ®iÒu ®ã vµ råi VÝc sÏ kiÓm tra xem c¸cquy ®Þnh cã tu©n thñ theo dßng ®ßi hái kh«ng.Chó ý r»ng mäi tÝnh to¸n cñaVÝc lµ theo thêi gian ®a thøc vµ tÝnh to¸n cña Peggy còng vËy ,miÔn lµ c« tabiÕt ®−îc sù tån t¹i cña mét phÐp t« 3 mÇu ф. Sau ®©y lµ mét vÝ dô nhá ®Ó minh ho¹:VÝ dô 13.3 Gi¶ sö G lµ mét ®å thÞ (V,E) trong ®ã : V = {1, 2, 3, 4, 5}vµ E = {12, 14, 15, 23, 34, 45}. Gi¶ sö Peggy biÕt phÐp t« 3 mÇu ? trong ®ã ф(1)=1, ф(2)= ф(4)=2,vµ ф(3)= ф (5)=3.Ta còng gi¶ sö r»ng c¸c tham sè cña s¬ ®å rµng buéc bÝtlµ n=321389 vµ m=156897 ,bëi vËy f(b,x)=mbx2 mod n,trong ®ã b=0,1 vµxєZn* . Gi¶ sö Peggy chän phÐp ho¸n vÞ Π =(1, 3, 5) ë mét vßng nµo ®ã chophÐp chøng minh. Khi ®ã c« ta tÝnh : C1 = 1 C2 = 3 C3 = 2 C4 = 3 C5 = 2vµ sÏ m· ho¸ phÐp t« mÇu nµy ë d¹nh nhÞ ph©n b»ng mét bé 10: 0111101110sau ®ã tÝnh c¸c rµng buéc cho 10 bÝt nµy .Gi¶ sö c« lµm nh− sau: b x F(b,x) 0 147658 176593 1 318856 205585 1 14497 189102 1 285764 294039 1 128589 230968 0 228569 77477 Trang 21Vietebooks Nguyễn Hoàng Cương 1 53369 305090 1 194634 276484 1 202445 292707 0 177561 290599Say ®ã Peggy trao cho Vic 10 gi¸ trÞ f(b,x) ®· tÝnh ë trªn TiÕp theo ,gi¶ sö r»ng VÝc chän c¹nh 34 lµm yªu cÇu cña m×nh.Sau ®ãPeggy sÏ më 4 blob :2 lob øng víi ®×nh 3 ,2 lob øng víi ®Ønh 4.Nh− vËyPeggy sÏ trao cho VÝc c¸c cÆp ®−îc s¾p sau: (b,x) = (1,128089), (0, 228569), (1, 53369), (1, 194634) VÝc sÏ kiÓm tratr−íc hÕt xem 2 mÊu cã kh¸c nhau kh«ng :10 lµ m·ho¸ cña mÇu 2 vµ 11 lµ m· ho¸ cña mÇu 3 .Nh− vËy diÒu võa kiÓm tra lµ ®−îcthá m·n. TiÕp theo, VÝc sÏ kiÓm tra thÊy r»ng 4 cam kÕt lµ hîp lÖ.§©y lµ ®iÒuph¶i chøng minh. Còng nh− trong c¸c hÖ thèng chøng minh ®· ®−îc nghiªn cøu ë trªnVÝc sÏ chÊp nhËn mét phÐp chøng minh hîp lÖ víi x¸c suÊt =1 ,bëi vËy ta cã®−îc tÝnh ®Çy ®ñ .X¸c suÊt ®Ó VÝc sÏ chÊp nhËn b»ng bao nhiªunÕu G kh«ngthÓ t« b»ng 3 mÇu ? Trong tr−êng hîp nµy ,®èi víi phÕp t« mÇu bÊt k× ph¶i cãÝt nh©ts mét c¹nh ij ®Ó i vµ j cã cïng mÇu .C¬ héi ®Ó VÝc chän mét c¹nh nh−vËy it nhÊt lµ 1/m.X¸c xuÊt ®Ó Peggy ®¸nh lõa ®−îc VÝc trong toµn bé m2vßng nhiÌu nhÊt lµ (1- 1/m )nv× (1- 1/m )m e-1 khi m ∞ nªn ta thÊy r»ng (1- 1/m )n e-m vµ gi¸ trÞ nµytiÕn tíi 0 theo hµm mò nh− lµ hµm cña m | E | .Bëi vËy ta còng cã ®−îc tÝnh®óng ®¾n. Trë l¹i xem xÐt khÝa c¹nh kh«ng tiÕt lé th«ng tin cña hÖ thèng chøng minh.TÊt c¶ nh÷ng c¸i mµ VÝc thÊy trong mçi vßng ®· cho cña giao thøc lµ métphÐp t« 3 mÇu ®· m· cña G, cïng víi hai mÇu ph©n biÖt cña c¸c ®Ønh trªnmét c¹nh cô thÓ nh− ®· ®−îc Peggy cam kÕt tr−íc ®ã. V× c¸c mÇu ®−îcho¸n vÞ ë mçi vßng nªn d−êng nh− lµ VÝc kh«ng thÓ kÕt hîp c¸c th«ng tin tõc¸c vßng kh¸c nhau ®Ó x©y dùng phÐp t« 3 mÇu . HÖ thèng chøng minh nµy kh«ng ph¶i lµ mét hÖ thèng chøng minh kh«ngtiÕt lé th«ng tin hoµn thiÖn mµ chØ lµ mét d¹ng yÕu h¬n cña nã vµ ®−îc gäi lµmét hÖ thèng chøng minh kh«ng tiÕt lé th«ng tin vÒ mÆt tÝnh to¸n .TÝnh Trang 22Vietebooks Nguyễn Hoàng Cươngkh«ng tiÕt lé th«ng vÒ mÆt tÝnh to¸n ®−îc ®Þnh nghÜa gièng nh− tÝnh kh«ngtiÕ lé th«ng tin hoµn thiÖn ngo¹i trõ mét ®iÓm lµ c¸c ph©n bè x¸c suÊt t−¬ngøng cña c¸c b¶n sao chØ ®ßi hái kh«ng ph©n ph©n biÖt theo ®a thøc (theo c¸chhiÓu ë ch−¬ng 12) chø kh«ng nhÊt thiÕt ph¶i lµ ®ång nhÊt . H×nh 12.13.mét hÖ thèng chøng minh t−¬ng hç kh«ng tiÕt lé th«ng tinvÒ mÆt tÝnh to¸n cho b¸i to¸n xÐt kh¶ n¨ng t« ®å thÞ b»ng 3 mÇu .§Çu vµo : Mét ®å thÞ G = (E,V) trªn tËp ®Ønh {1,. . .,n}1. lÆp l¹i c¸c b−íc sau m2 lÇn .2. Cho ф lµ mét ®å thÞ t« 3 mÇu cña G .Peggy sÏ chän mét ho¸n vÞ ngÉu nhiªn Π cña {1,2,3}.Víi 1≤i≤n,c« ta x¸c ®Þnh Ci = Π(ф(i)) Vµ viÕt ci nh− mét x©u bÝt cã ®é d¸i hai: Ci=ci1ci2 Sau ®ã ,víi i≤1≤n c« ta chän 2 phÇn tö ngÉu nhiªn ri1,ri2?thuéc X vµ tÝnh rij=f(cij,rij),j=1,2råi göi danh s¸ch cho VÝc (r11 ,r12 ,. . .,rn1 ,rn2)3. VÝc chän mét c¸ch ngÉu nhiªn {u,v} є E vµ göi nã cho Peggy.4. Peggy göi (cu1,cu2,ru1,ru2) vµ (cv1,cv2,rv1.r v2) cho VÝc.5. VÝc kiÓ ...