Các chứng minh không tiết lộ thông tin hệ thống chứng minh tương hỗ Một cách đơn giản, một hệ thống chứng minh không tiết lộ thông tin sẽ cho phép một đối tượng thuyết phục được một đối tượng khác tin một điều nào đó mà không để lộ một tý thông tin nào về phép chứng minh. | y r I ll r I X I 1 XV X I Á I I A I I A Giáo trình tin học Hướng dân các chứng minh mà không cân tiết lộ thông tin HỆ THỐNG CHÚNG MINH TƯƠNG Hỗ Một cách đơn giản một hệ thống chứng minh không tiết lô thông tin sẽ cho phép một đối tượng thuyết phục được một đối tượng khác tin một điều nào đó mà không để lộ một tý thông tin nào về phép chứng minh. Trước tiên ta sẽ thảo luận ý tưởng về một hệ thống chứng minh tương hỗ. Trong một hệ thống chứng minh tương hỗ có hai thành viên teggy và Vic. Teggy là người chứng minh và Vic là người kiểm tra. Teggy biết một điều gì đó và cô ta muốn chứng minh cho Vic rằng cô ta biết điều đó. Điều cần thiết là phải mô tả được các kiểu tính toán mà Peggy và Vic được phép thực hiện và các tác động qua lại xảy ra. Ta có thể coi các thuật toán mà Peggy và Vic thực hiện là các thuật toán xác suất. Peggy và Vic sẽ thực hiện các tính toán riêng và mỗi người đều có một bộ tạo số ngẫu nhiên riêng. Họ sẽ liên lạc với nhau qua một kênh truyền tin. Thoạt đầu cả Peggy và Vic đều có một giá trị x. mục đích của phép chứng minh tương hỗ là Peggy phải thuyết Vic rằng x có một tính chất xác đình nào đó. Chính xác hơn x là câu trả lời có của một bái toán quyết định xác định n. Phép chứng minh tương hỗ là một giao thức hỏi-đáp gồm một số vòng xác định. Trong mỗi vòng .Peggy và Vic luân phiên thực hiện các công việc sau 1. Nhận một thông báo từ nhóm khác . 2. Thực hiện một tính toán riêng. 3. Gửi một thông báo toiư nhóm khác Một vòng điển hình của giao thức sẽ gồm một yêu cầu của Vic và một đáp ứng của Peggy. Tới cuối phép chứng minh Vic hoặc sẽ chấp nhận hoặc từ chối tuỳ thuộc vào việc liệu Peggy có đáp ứng thành công các yêu câù của Vic hay không. Ta định nghĩa giao thức là một hệ thông chứng minh tương hỗ đối với vái toán quyết định n nếu hai tính chất sau được thoả mãn mỗi khi Vic tuân theo giao thức đó Tính đầy đủ Trang 1 Vietebooks Nguyễn Hoàng Cương Nếu x là câu trả lời có của hai bái toán quyết định n thì Vic sẽ luôn luôn chấp nhận chứng minh
