Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Hướng dẫn các chứng minh mà không cần tiết lộ thông tin phần 5 pps
Nội dung xem thử
Mô tả chi tiết
Vietebooks Nguyễn Hoàng Cương
Trang 21
®Þ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Çu
Peggy më c¸c blob øng víi c¸c ®iÓm cuèi cña mét c¹nh nµo ®ã ®−îc chän
ngÉu nhiªn.Peggy sÏ thùc hiÖn c¸c ®iÒu ®ã vµ råi VÝc sÏ kiÓm tra xem c¸c
quy ®Þnh cã tu©n thñ theo dßng ®ßi hái kh«ng.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
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Ýt
lµ n=321389 vµ m=156897 ,bëi vËy f(b,x)=mb
x2
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 ®ã cho
phÐp chøng minh. Khi ®ã c« ta tÝnh :
C1 = 1
C2 = 3
C3 = 2
C4 = 3
C5 = 2
vµ sÏ m· ho¸ phÐp t« mÇu nµy ë d¹nh nhÞ ph©n b»ng mét bé 10:
0 1 1 1 1 0 1 1 1 0
sau ®ã 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
1
1
1
1
0
147658
318856
14497
285764
128589
228569
176593
205585
189102
294039
230968
77477