Đ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 2

Tất cả các tính toán của Vic có thể thực hiện được trong thời gian đa thức (như một hàm của n là số các đỉnh trong G1 và G2). | Vietebooks Nguyễn Hoàng Cương mỗi vòng và ghi một bản sao đẳng cấu ngẫu nhiên của G1 lên băng liên lạc. Xác suất để Peggy giả định đúng các yêu cầu của Vic là 2n. Tất cả các tính toán của Vic có thể thực hiện được trong thời gian đa thức như một hàm của n là số các đỉnh trong G1 và G2 . Mặc dù không cần thiết lắm nhưng ta cũng thấy rằng các tính toán của Peggy cũng có thể được thực hiện trong thời gian đa thức miễn là cô ta biết được sự tồn tại của phép hoán vị ỗ là G1. Tại sao ta lại coi hệ thống chứng minh là hệ thông chứng minh không tiết lộ thông tin. Lý do là ở chỗ mặc dù Vic đã bị thuyết phục rằng G1 là đẳng cấu với G2 nhưng anh ta vẫn không thu thêm được tý kiến thức nào để giúp tìm được phép hoán vị ỗ đưa G2 về G1. Tất cả những điều mà Vic thấy trong mỗi vòng của phép chứng minh là một bản sao ngẫu nhiên của các độ thị này mà không cần tới sự giúp đỡ của Peggy. Vì các đồ thị H được chọn một cách độc lập và ngẫy nhiên ở mỗi phần của phép chứng minh nên điều này không giúp đỡ được gì vho Vic trong việc tìm một phép dẳng cấu từ G1 sang G2. Ta hãy xem xét kĩ lưỡng thông tin mà Vic thu được nhờ tham gia vào hệ thông chứng minh tương hỗ. Có thể biểu thị cách nhình của Vic về phép chứng minh tương bằng một bản sao chứa các thông tin sau 1. Các đồ thị G1 và G2 2. Tất cả các thông báo được Peggy và Vic gửi đi. 3. Các số ngẫu nhiên mà Vic dùng để tào các yêu cầu của mình. Bởi vậy một bản sao T đối với phép chứng minh tương hỗ về phép đẳng cấu đồ thị sẽ có dạng sau T G1 G2 H1 ii pi . . . Hn in pn Điểm mấu chốt tạo cơ sở cho định nghĩa hình thức về phép chứng minh không tiết lộ thông tin là Vic hay vất kỳ người nào khác có thể giả mạo Trang 6 Vietebooks Nguyễn Hoàng Cương các bản sao mà không cần phải tham gia vào hệ chứng minh tương hỗ giống như các bản sao thực tế. Điều này có thể thực hiện được miễn là các đồ thị G1 và G2 là đẳng cấu. Việc giả mạo được thực hiện theo thuật toán mô tả trên hình 13.6. thuật toán giả mạo là một thuật toán xác suất theo thời gian đã .