Download miễn phí Bài giảng Các chứng minh không tiết lộ thông tin



Hệ thống chứng minh không tiết lộ thông tin đối với bái toán đẳng cấu
đồ thị là một hệ thống thú vị, tuy nhiênsẽ là hữu ích hơn nếu có các hệ thống
chứng minh không tiết lộ thông tin cho các bái toán được coi là NP đầy đủ.
Về mặt lý thuyết, không tồn tại các phép chứng minh không tiết lộ thông tin
hoàn thiện cho các bái toán NP đầy đủ. Tuy nhiên ta có thể mô tả các hệ
thống chứng minh có dạng không tiết lộ thông tin về mặt tính toán. Các hệ
thống chứng minh thực tế sẽ được mô tả ở phần sau ; trong phần này ta sẽ mô
tả kỹ thuật cam kết bít là một công cụ quan trọng được dùng trong hệ thống
chứng minh


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-02-25-bai_giang_cac_chung_minh_khong_tiet_lo_thong_tin.3e516HAtAM.swf /tai-lieu/de-tai-ung-dung-tren-liketly-59056/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

hỏi giao thức?.
Trong tr−ờng hợp phép đẳng cấu đồ thị, cách duy nhất mà Vic có thể
đi chệch khỏi giao thức chọn các yêu cầu i của mình theo cách không ngẫu
nhiên. về mặt trực giác có vẻ nh− đIều này không cung cấp cho Vic một chút
“hiểu biết” nào. Tuy nhiên các bản sao đ−ợc tạo bởi bộ mô phỏng sẽ không
còn giống nh− các bản sao do Vic tạo ra nếu anh ta đi chệch khỏi giao thức.
Ví dụ ,giả sử Vic chọn i = 1 trong mỗi vòng vủa phép chứng minh. Khi đó
một bản sao của phép chứng minh t−ơng hỗ sẽ có ij = 1 với 1 ≤ j ≤ n, trong
Vietebooks Nguyễn Hoàng Cương
Trang 10
khi đó một bản sao đ−ợc tào bởi bộ mô phỏng sẽ có ij = 1 với 1 ≤ j ≤ n, chỉ
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 nh−ng 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ỗ th−o 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 hay 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
t−ơng hỗ. T−ơng tự ,với T∈F(x), cho ????(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 T(V*,x)và với bất kỳ kỳ T ∈
??????(V*,x), giả sử rằng pFv(T) =?????(T). khi đó hệ thống chứng minh
t−ơng hỗ đ−ợc gọi là một hệ thống chứng minh không tiết lộ thông tin hoàn
thiện(không điều kiện).
Trong hợp đặc biệt khi V* giống nh− Vic (khi Vic là trung thực) thì
định nghĩa trên giống nh− định nghĩa 13.1.
Hình 13.7 thuật toán giả mạo cho V* đối với các bản sao cho tnsh
đẳng cấu đồ thị
Vietebooks Nguyễn Hoàng Cương
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 ij 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 (Hj, ịj, ρj) và
thực hiện thuật toán V* đẻ thấy đ−ợc yêu cầu của nó dành cho vòng j. nếu giả
định ij giống nh− yêu cầu i’j(nh− đ−ợc tạo bởi V*) thì bộ ba (Hj, ịj, ρj) sẽ
đ−ợc gắn vào bản sao giả mạo. nếu không thị bộ ba này sẽ bị loại bỏ, S* sẽ
giả định một yêu cầu mới ij và thuật toán V* sẽ đ−ợc khởi động lại sau khi
thiết lập lại trạng thái của nó về tràng thái bắt đầu của vòng hiện thời . thuật
ngữ “trạng thái ”đ−ợc hiểu là các giá trị của tất cả các biến dùng trong thuật
toán.
Bây giờ ta sẽ đ−a ra một mô tả chi tiết hơn về thuật toán mô phỏng S*.ở
thời đIúm bát kỳ cho tr−ớc, trong khi thực hiên ch−ơng trình V* trạng thái
hiện thời của V* sẽ đ−ợc ký hiệu là state (V*). Một mô tả giả mã của thuật
toán mô phỏng đ−ợc cho ở hình 13.7
Đầu vào: hai đồ thị đẳng cấu G1 và G2 ,mỗi đồ thị có tập đỉnh {1...n}
1. T = (G1, G2)
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 ij=1 hay 2
6. Chọn pj là phép hoán vị ngẫu nhiên của {1...n}
7. Tính Hj là ảnh của Gi theo ρj
8. Gọi V* với đầu vào Hj ta thu đ−ợc một yêu cầu I’,
9. If ij = I’j then
ghép (Hj, ij, ρj) vào đuôi của T
Else
Thiết lập lại V* bằng cách xác định trạng thái (V*)
= trạng thái cũ
10. Until ij=i’j
Vietebooks Nguyễn Hoàng Cương
Trang 12
Có khả năng bộ mô phỏng sẽ không dừng lại nếu không xảy ra ij = i’j.
tuy nhiên có thể chứng tỏ rằng thời gian chạy trung bình của bộ mô phỏng là
thời gian đa thức và hai phân bố xác suất ????????(T)và ???????(T)là đồng
nhất.
Đị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 hay 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
vòng. Với 0 ≤ j ≤ n ta xác định các phân bố xác xuất pτ,v,j(T) và pτ,v,n(T) trên
tập các bản sao bộ phận Tj xuất hiện ở cuối vòng j. Chú ý rằng pτ,v,j(T) =
pτ,v(T)và pτ,v,n(T) = pτ,v(T). Bởi vậy nếu có thể chứng tỏ rằng hai phân bố
pτ,v,j(T) và pτ,v,j(T) là đồng nhất với mọi j thì ta có điều cần chứng minh .
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ị G1 và G2 .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 Nguyễn Hoàng Cương
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 .
Xét điều sẽ xảy ra trong vòng j của phép ch...

---