Đang chuẩn bị liên kết để tải về 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 3

Đầu vào: hai đồ thị đẳng cấu G1 và G2 ,mỗi đồ thị có tập đỉnh {1.n} 1. 2. 3. 4. 5. 6. 7. 8. 9. T = (G1, G2) For j = 1 to n do Xác định tàng thái cũ bằng trạng thái (V*) Repeat Chọn ngẫu ij=1 hoặc 2 Chọn pj là phép hoán vị ngẫu nhiên của {1.n} | Vietebooks Nguyễn Hoàng Cương Đầu vào hai đồ thị đẳng cấu G1 và G2 mỗi đồ thị có tập đỉnh 1.n 1. T G1 G2 2. For j 1 to n do 3. Xác định tàng thái cũ bằng trạng thái V 4. Repeat 5. Chọn ngẫu ij 1 hoặc 2 6. Chọn Pj là phép hoán vị ngẫu nhiên của 1.n 7. Tính Hj là ảnh của Gi theo Pj 8. Gọi V với đầu vào Hj ta thu được một yêu cầu I 9. If ij I j then ghép Hj ij Pj vào đuôi của T Else Thiết lập lại V bằng cách xác định trạng thái V trạng thái cũ 10. Until ij i j Để chứng minh rằng hệ thống chứng minh là không tiết lộ thông tin hoàn thiện ta cần một phép biến đổi chung để xây dựng một bộ mô phỏng S từ V bất kỳ. Ta sẽ tiếp tục thực hiện việc này đối với hệ thống chứng minh cho tính đẳng cấu đồ thị. Bộ mô phỏng sẽ đóng vai trò của Peggy sử dụng V như một chương trình con có khả năng khởi tạo lại. Nói một cách không hình thức S sẽ cố gắng giả định một yêu cầu ij mà V sẽ đưa ra trong mỗi vòng j. tức là S sẽ tạo ra một bộ ba hợp lệ ngẫu nhiên có dạng Hj ịj Pj và thực hiện thuật toán V đẻ thấy được yêu cầu của nó dành cho vòng j. nếu giả định ij giống như yêu cầu i j như được tạo bởi V thì bộ ba Hj ịj Pj sẽ được gắn vào bản sao giả mạo. nếu không thị bộ ba này sẽ bị loại bỏ S sẽ giả định một yêu cầu mới ij và thuật toán V sẽ được khởi động lại sau khi thiết lập lại trạng thái của nó về tràng thái bắt đầu của vòng hiện thời . thuật ngữ trạng thái được hiểu là các giá trị của tất cả các biến dùng trong thuật toán. Bây giờ ta sẽ đưa ra một mô tả chi tiết hơn về thuật toán mô phỏng S .ở thời đlúm bát kỳ cho trước trong khi thực hiên chương trình V trạng thái hiện thời của V sẽ được ký hiệu là state V . Một mô tả giả mã của thuật toán mô phỏng được cho ở hình 13.7 Trang 11 Vietebooks Nguyễn Hoàng Cương Có khả năng bộ mô phỏng sẽ không dừng lại nếu không xảy ra ij i j. tuy nhiên có thể chứng tỏ rằng thời gian chạy trung bình của bộ mô phỏng là thời gian đa thức và hai phân bố xác suất T và T là đồng nhất. Định lý 13.2 Hệ thống chứng minh tương hỗ cho tính đẳng cấu đồ thị là một hệ .