Vietebooks Nguyn Hong Cng
Trang 6
mỗi vòng và ghi một bản sao đẳng cấu (ngẫu nhiên ) của G
1
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à 2
n
. ??????????????????????????????
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 G
1
và G
2
). Mặc dù không cần
thiết lắm nhng 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à G
1
.

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 G


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 = ((G
1
, G
2
):(H
1
, i
1
, p
1
): . . . (H
n
, i
n
, p
n
))

Đ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
Vietebooks Nguyn Hong Cng
Trang 7
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ị G
1

Giả sử ta có một chứng minh tơng hỗ thời gian đa thức cho bái toán
quyết định

và một bộ mô phỏng thời gian đa thức S. Kí hiệu tập tất cả các
bản sao có thể cho kết quả có x là F(x). Các bản sao giả mạo có thể đợc tạo
bởi S là F(x). với bản sao bất kỳ T

)(x

,cho bản sao giả mạo có thể đợc tạo
bởi S là F(x). với bản sao bất kì T
)(x


cho p

(T) là xác suất để T là một
bản sao đợc tạo từ phép chứng minh tơng hỗ. Tơong tự, với T

F(x), cho
p

(T) là xác suất để T là một bản sao (giả mạo) đợc tạo bởi S, Giả sử rằng
)()( xFx =

và với bất kỳ T


)(x



Dĩ nhiên là có thể định nghĩa đặc tính không tiết lộ thông tin theo kiểu
mà ta thiéc. Tuy nhiên điều quan trọng là định nghĩa phải giữ nội dung cơ
bản của đặc tính này. Ta đã coi rằng một hệ thống chứng minh tơng hỗ là hệ
không tiết lộ thông tin cho Vic nếu tồn tại một hệ mô phỏng rạo ra các bản
sao có phân bố xác suất đồng nhất với phân bố xác suất của các bản sao
đợc tạo ra khi Vic tham gia thực sự vào giao thức. (đây là một khái niêm
tơng đối nhng mạnh hơn khái niệm về các phân mốt xác suất không có khả
năng phân biệt nêu trong chơng 12). Ta đã biết rằng một bản sao sẽ chứa tất
cả các thông tin mà Vic thu lợm đợc nhờ tham gia vào giao thức. Bởi vậy,
quả là hợp lý khi ta xem rằng bất cứ việc gì mà Vic có thể thực hiện đợc sau
khi tham gia vào gia thức cũng chỉ nh việc mà anh ta có thể thực hiện đợc
nếu sử dụng hệ mô phỏng để tào một bản sao giả mạo. Mặc dù ta không định
nghĩa thông tin(hiểu biết )bằng cách tiếp cận này nhng bất cứ đIều gì
đợc coi là thông tin thì Vic không thu lợm đợc tý nào!

Bây giờ ta sẽ chứng tỏ rằng hệ thống chứng minh tơng hỗ đối với tính
đẳng cấu đồ thị là một hệ thống chứng minh không tiết lộ thông tin đối với
Vic.

Định lý 13.1

Hệ thông chứng minh tơng hỗ đối với tính đẳng cấu đồ thị là một hệ
thống chứng minh không tiết lộ thông tin hoàn thiện đối với Vic. Chứng minh: Đầu vào : hai đồ thị G1 và G2 mỗi đồ thị có tập đỉnh {1 n}

là các đồ thị đẳng cấu có n đỉnh. Một bản sao T (thực hoặc
giả mạo) sẽ gồm n bộ dạng(H, i, )trong đó i=1 hoặc 2, p là một phép hoán vị
của {1, ,n} và H là ảnh của G
1
theo hoán vị . Ta goim một bộ ba nh vậy là
một bộ ba hợp lệ và ký hiệu nó là ????????????. Trớc tiên ta sẽ tính |??????|
là số các bộ ba hợp lệ. Hiển nhiên là |????| = 2ìn! vì mỗi phép chọn i và p sẽ
xác định một đồ thị duy nhất H.

ở mỗi vòng cho trớc j bất kỳ của thuật toán giả mạo rõ ràng là mỗi bộ
ba hợp lệ (H, i, )là bộ ba thứ j ở bản sao thực là gì? Trong hệ thống chứng
minh tơng hỗ, trớc tiên Peggy dẽ chọn một phép hoán vị ngẫu nhiên sau
đó tính H là ảnh của G
1
theo . Phéhoán vị p đợc xác định là nếu i = 1và
nó đựoc xác định là hợp của hai phép hoán vị nếu i = 2.

Giả sử giá trị vủa i đợc chọn ngẫu nhiên bởi Vic. Nếu i = 1 thì tất cả
n! phép hoán vị là đồ các suất vì trong trờng hợp này = và đã đợc
chọn là một phép hoán vị ngẫu nhiên. Mặt khác, nếu i = 2 thì =
0
,trong
đó là ngẫu nhiên và là cố định. Trong trờng hợp này mỗi phép hoán vị
có thể đều có xác suất bằng nhau. Xét thấy, vì cả hai trờng hợp i = 1 và i = 2
đều vào xác suất bằng nhau và mỗi phép hoán vị đồng xác suất (không phụ
thuộc vào giá trị của i) và bởi vì i và p cùng xác định H nên suy ra mọi bộ ba
trong R chắc chắn sẽ đồng xác suất.

Vì một bản sao gồm n bộ ngẫu nhiên độc lập ghép với nhau nên đối
với mỗi bản sao có thể có T ta có:

với xác suất xuất hiện bằng2.

Điều khó khăn ở đây là phải chứng tỏ rằng cho dù Vic không trung
thực đi chệch khỏi giao thức nhng vẫn tồn tại trong bộ mô phỏng thời gian
với thời gian đa thức tạo ra các bản sao giả mạo giống nh các bản sao đợc
tạo bởi Peggy và Vic (không trung thực) trong phép chứng minh tơng hỗ.
Cũng nh ở trên, câu giống nh đợc hình thức hoá bằng cách nói rằng hai
phân bố xacs suất này là đồng nhất.

Sau đây là một định nghĩa hình thức hơn nữa.

Định nghĩa13.2

Giả sử rằng ta có một hệ thống chứng minh tơng hỗ tho thời gian đa
thức cho một bái toán quyết định cho trớc

. Cho V* là một thuật toán xác
suất theo thời gian đa thức mà ngời kiểm tra (có thể không trung thực)sử
dụng dể tào các yêu cầu của mình (tức là V* biểu thị cho một ngời kiểm tra
trung thực hoặc không trung thực). Ký hiệu tập tất cả các bản sao có thể
(đợc tào ra do kết quả của phép chứng minh tơng hỗ mà Peggy và V* thực
hiện với câu trả lời có x của

) là ?????(V*,x). giả sử rằng với mỗi V* nh
vậy tồn tại một thuật toán xác suất theo thời gian đa thức S*=S*(V*) (bộ mô
phỏng) tạo ra một bản sao giả mạo. ký hiệu tập các bản sao giả mạo có thể
bằng ???(V*,x). Với một bản sao bất kỳ T

???? (V*,x) cho ???(T) là xác
suât để T là một bản sao dó V* tạo ra ki tham gia vào phép chứng minh