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
Tài liệu đang bị lỗi
File tài liệu này hiện đang bị hỏng, chúng tôi đang cố gắng khắc phục.
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