Vietebooks Nguyn Hong Cng
Trang 11 Để chứng minh rằng hệ thống chứng minh là không tiết lộ thông tin
hoàn thiện ta cần một phép biến đổi chung để xây dựng một bộ mô phỏng S*
từ V* bất kỳ. Ta sẽ tiếp tục thực hiện việc này đối với hệ thống chứng minh
cho tính đẳng cấu đồ thị. Bộ mô phỏng sẽ đóng vai trò của Peggy sử dụng V*
nh một chơng trình con có khả năng khởi tạo lại. Nói một cách không
hình thức S* sẽ cố gắng giả định một yêu cầu i
j
mà V*sẽ đa ra trong mỗi
vòng j. tức là S* sẽ tạo ra một bộ ba hợp lệ ngẫu nhiên có dạng (H
Đầu vào: hai đồ thị đẳng cấu G1 và G2 ,mỗi đồ thị có tập đỉnh {1 n}

1. T = (G
1
, G
2
)
2. For j = 1 to n do
3. Xác định tàng thái cũ bằng trạng thái (V*)
4. Repeat
5. Chọn ngẫu i
j
=1 hoặc 2
6. Chọn p
j
là phép hoán vị ngẫu nhiên của {1 n}
7. Tính H
j
là ảnh của G
i
theo
j

8. Gọi V* với đầu vào H
j
ta thu đợc một yêu cầu I,
9. If i
j

Định lý 13.2

Hệ thống chứng minh tơng hỗ cho 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.

Chứng minh:

Trớc tiên ta thấy rằng bất luận V* tạo ra các yêu cầu của nó ra sao,
xác suất để giả định i
j
là bằng 1/2. Nh vậy trung bình S* phảI tạo đợc hai
bộ ba để tạo đợc hai bộ ba ,để tạo đợc một bộ ba gắn voà bản sao giả mạo.
Do đó thời gian chạy trung bình là thời gian đa thức theo n .

Nhiệm vụ khó khăn hơn là phảI chứng tỏ rằng hai phân bố xác suất
????????(T)và ????????????(T) là nh nhau.ở định lý 13.1(trong đó Vic là
ngời kiểm tra trung thực) ta đã tính đợc hai phân bố xác suất và thấy rằng
chúng là đồng nhất. Ta cũng đã sử dụng một yếu tố là các bộ ba (H, i, )
đợc ở các vòng khác nhau của phép chứng minh là độc lập. Tuy nhiên trong
bái toán này ta không có cách tính toán tờng minh hai phân bố xác suất.
Hơn nữa các bộ ba đợc tạo ở các vòng khác nhau của phép chứng minh lại
không độc lập. Ví dụ yêu cầu mà V
*
đa ra vòng j có thể phụ phuộc theo 1
kiểu rất phức tạp nào đó vào các yêu cầu ở các vòng trớc và vào cách Peggy
đáp ứng các yêu cầu đó.

Cách khắc phục các khó khăn này là phải xem xét các phân bố xác
xuất trên các bản sao bộ phận có thể có trong quá trình mô phỏng hoặc chứng
minh tơng hỗ và sau đó tiếp tục bằng phơng pháp quy nạp trên số các

Trờng hợp j = 0 ứng với khi bắt đầu thuật toán : lúc này bản sao chỉ gồm
hai đồ thị G
1
và G
2
.Bởi vậy các phân bố xác suất là đồng nhất khi j = 0 .Ta sẽ
sử dụng điều kiện để bắt đầu phép quy nạp.
Vietebooks Nguyn Hong Cng
Trang 13
Trớc tiên ta giả sử hai phân bố xác suất p

,v,j-1
(T)
,
và p

,v,j-1
(T) trên
j-1
là
đồng nhất với giá trị j 1 nào đó. Sau đó ta sẽ chứng tỏ rằng hai phân bố xác
suất p

,v,j
(T) và p

,v,j
(T) trên
j
là đồng nhất .

/2 ;
xác suất để i=2 và yêu cầu của V là 2 bằng (1-p
j
)/2. ở mỗi trạng thái này, (H,
i, ) đợc coi là bộ ba thứ j của bản sao. Với xác suất bằng 1/2 sẽ không có gì
đợc viết tiếp lên băng trong lần lặp cho trớc bất kỳ của vòng lặp REPEAT .

Trớc hết sẽ xét trờng hợp i =1. Nh đã nêu ở trên, xác suất để yêu
cầu của V=1 là p
1
. Xác suất để một bộ ba (H,i,p) đợc coi là bộ ba thứ j trong
bản sao ((H,i,p) đợc viết tiếp lên bảng) trong bớc lặp thứ i của vòng lặp
REPEAT bằng: Bởi vậy, Xác suất để (H, i, ) là bộ ba thứ j trong bản sao là:
Trờng hợp i = 2 đợc phân tích theo cách tơng tự : Xác suất để
(H,i,p) đợc coi là bộ ba thứ j trong bản sao bằng (1-p
1
)/n!.

n!2
1
P
ì
l
n!

,v,j-1
(T)

là nh
nhau. Định lý đợc chứng minh

Việc xem xét hệ thống chứng minh tơng hỗ đối với tính không đẳng
cấu đồ thị cũng rất thú vị. Không quá khó khăn để chứng minh rằng, hệ thống
chứng minh này là hệ thống không tiết lộ thông tin hoàn thiện nếu Vic tuân
thủ giao thức ( tức là nếu Vic chọn mỗi đồ thị yêu cầu là một phiên bản đẳng
cấu ngẫu nhiên của G
1
, trong đó i =1 hoặc i =2 đợc chọn ngẫu nhiên ). Hơn
nữa nếu là Vic tạo mỗi đồ thị yêu cầu bằng cách lấy một phiên bản đẳng cấu
của G
1
hoặc G
2
thì giao thức vẫn đảm bảo không tiết lộ thông tin ngay cả khi
Vic chọn các yêu cầu của mình một cách không ngẫu nhiên. Tuy nhiên, giả
sử rằng, kẻ gây rối Oscar đa cho Vic một đồ thị H ( H là đẳng cấu với G
1

hoặc G
2
) nhng Vic không biết G
i
nào là đẳng cấu với H nếu Vic sử dụng H
này làm một trong các đồ thị yêu cầu của mình trong các hệ thống chứng
minh tơng hỗ thì Peggy sẽ cho Vic một phép đẳng cấu mà trớc đó anh ta
Peggy đang phải chứng tỏ x là một thặng d bậc hai. ở mỗi vòng cô ta sẽ
tạo ra một thặng d bậc hai ngẫu nhiên y và gửi nó cho Vic. Sau đó tuỳ thuộc
vào yêu cầu của Vic, Peggy hoặc sẽ đa cho Vic một căn bậc hai của y hoặc
một căn bậc hai của xy.

Rõ ràng là giao thức đầy đủ. Để chứng minh tính đúng đắn ta thấy rằng
nếu x không phải là một thặng d bậc hai thì Peeggy chỉ có thể trả lời một
trong hai yêu cầu có thể vì trong trờng hợp này y là một thặng d bậc hai
khi và chỉ khi xy không phải một thặng d bậc hai. Bởi vậy Peggy sẽ bị tóm ở
một vòng cho trớc bất kỳ của giao thức với xác suất 1/2 và xác suất để
Peggy đánh lừa đợc Vic trong toàn bộ n vòng chỉ bằng = 1/n ( lý
do có log
2

mod n.
Peggy gửi y cho Vic.
3. Vic chọn một số ngẫu nhiêni = 0 hoặc i = 1 và gửi nó cho Peggy.
4. Peggy tính
z = u
j
v mod n,
trong đó u là căn bậc hai của x và gửi z cho Vic .
5. Vic kiểm tra xem liệu có thoả mãn :
z
2
x
i
y(mod n).
6. Vic sẽ chấp nhận chứng minh của Peeggy nếu tính toán ở bớc 5
đợc kiểm tra cho mỗi vòng (trong log
2
n vòng ) .
nlog
2
2