Vietebooks Nguyn Hong Cng
Trang 1
Chơng 13

Các chứng minh không tiết lộ thông tin

13.1.các 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 .

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.

Hình 13.1 . tính đẳng cấu đồ thị Sau đây sẽ trình bày một hệ thống chứng minh tơng hỗ cho phép Peggy
chứng tỏ với Vic rằng 2 đồ thị chỉ ra là không đẳng cấu. Để đơn giản, giả sử
rằng mỗi đồ thị G1 và G2 có tập đỉnh {1 n}. Hệ thông chứng minh tơng hỗ
đối với tính không đẳng cấu đồ thị đợc mô tả trên hình 13.2.
Đặc trng của bái toán : 2 đồ thị n đỉnh G
1
=(V
1
,E

Hình 13.3 các đồ thị không đẳng cấu của Peggy và yêu cầu của Vic

?????????????????????

) trong đó V = (1, 2, 3, 4), E
1
= {12, 14,
23, 34}, E2 ={112,13,14,34}.

Gỉa sử ở một vòng nào đó của giao thức,Vic trao cho Peggy đồ thị
H=(V, E
3
) trong đó E
3
={13, 14, 23, 24}(xem hình 13.3). Đồ thị H là đẳng
cấu với G
1
. (Một phép đẳng cấu từ H vào G1 là phéo hoán vị (1 3 4 2)). Bởi
vậy Peggy sẽ trả lời 1

Dễ dàng nhận thấy rằng, hệ thống chứng minh này thoả mãn tính đầy đủ
và tính đúng đắn. Nếu G
1
không đẳng cấu với G
2
thì j sẽ bằng i ở mỗi vòng và
Vic sẽ chấp nhận với xác suất 1. Bởi vậy giao thức là đầy đủ.

Mặt khác, giả sử rằng G
1
đẳng cấu với G
2
. Khi đó một đồ thị yêu cầu bất
kỳ H đợc Vic đa ra đẳng cấu với cả G

là Peggy phảI thuyết phục Vic rằng x có một tính chất xác định nào đó,
nhng vào lúc kết thúc giao thức Vic vẫn không có chút ý niệm nào về cách
chứng minh (cho chính anh ta ) rằng có tính chất đó. Đây là một khái niệm
rất khó định nghĩa hình thức ,bởi vậy ta sẽ đa ra trớc khi định nghĩa nó.
Trên hình 13.4 mô tả một phép chứng minh tơng hỗ không tiết lộ thông tin
đối với tính đẳng cấu của đồ thị. Ví dụ nhỏ sau sẽ minh hoạ cho hoạt động
của thuật toán.
Vietebooks Nguyn Hong Cng
Trang 5

theo có phải là H không. Nếu yêu cầu của Vic
là i=2 thì thì Peggy sẽ cho Vic phép hợp p=
0
=(3 2 1 4) và Vic sẽ kiểm tra
xem ảnh của G2 theo p có phải là H không.

Dễ dàng diểm tra đợc tính đầy đủ và tính đúng đắn của giao thức.
Không khó khăn thấy rằng xác suất để Vic chấp nhận sẽ bằng 1 nếu G
1
đẳng
cấu với G
2
. Mặt khác nếu G
1
không đẳng cấu với G2 thì chỉ có một cách để
Peggy lừa dối đợc Vic là có ta phải giả định đúng giá trị i mà Vic sẽ chọn ở Đầu vào :hai đồ thị G1 và G2 mỗi đồ thị có tập đỉnh {1 n}
1. Lặp lại các bớc sau n lần
2. Peggy chọn một phứp hoán vị ngẫy nhiên vủa {1 n} cô ta
tính H là ảnh của G
1
theo và gửi H cho Vic
3. Vic chọn một số nguyên ngẫu nhiên I=1 hoặc 2 và gửi nó
cho Peggy
4. Peggy tính một phép hoán vị của {1 n} sao cho H là ảnh
của G
1
theo p. Peggy sẽ gửu p cho Vic (nếu i= 1 thì Peggy sẽ