Đ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 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 | Vietebooks 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ầ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 mbx2 mod n trong đó b 0 1 và xeZn . Giả sử Peggy chọn phép hoán vị n 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 147658 176593 1 318856 205585 1 14497 189102 1 285764 294039 1 128589 230968 0 228569 77477 Trang 21 Vietebooks Nguyễn Hoàng Cương 1 53369 305090 1 194634 276484 1 202445 292707 0 177561 290599 Say đó 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.Nhu vậy Peggy 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à được thỏ 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ều phải chứng minh. Cũng như trong các hệ thống chứng minh đã được nghiên cứu ở trên Ví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ông thể tô bằng 3 mầu Trong trường hợp này đối với .