Vietebooks Nguyn Hong Cng
Trang 16

Các bộ ba đợc tạo theo cách này có cùng phân bố xác suất các bộ ba
đợc tạo trong giao thức với giả thiết Vic chọn các yêu cầu của mình một
cách ngẫu nhiên. Tính không tiết lộ thông tin hoàn thiện (với v tuỳ ý) có thể
đợc chứng minh theo phơng pháp tơng tự nh đối với bái toán đẳng cấu
đồ thị. Nó đòi hỏi phải xây dựng một bộ mô phỏng s để giả định các yêu cầu
của v và chỉ giữ lại các bộ ba ứng với các giả định đúng.

Để minh hoạ thêm cho vấn đề này ta sẽ đa ra một ví dụ nữa về phép
chứng minh không tiết lộ thông tin hoàn thiện, đây là một phép chứng minh
cho một bái toán quyết định có liên quan đến bái toán logarit rời rạc. Bái toán
này đợc gọi là bái toán thành viên của nhóm con ( đợc mô tả ở hình 13.9 ).
Dĩ nhiên là số nguyên k ( nếu nó tồn tại ) chính là logarit rời rạc của

Hình 13.9. Thành viên của nhóm con.
Hình 13.10 Mô tả một phép chứng minh không tiết lộ thông tin hoàn
thiện cho bái toán thành viên nhóm con. Việc phân tích giao thức nỳ tơng tự


13.3 Các cam kết bít

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ên sẽ 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 .

Giả sử Peggy viết một thông báo lên một mẩu giấy rôì đặt nó vào một
két sắt mà cô ta biết mã số. Sau đó Peggy trao két sắt cho Vic. Mặc dù Vic

i
(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 .
Vietebooks Nguyn Hong Cng
Trang 18
Giả sử thông báo là một bít = 0 và Peggy sẽ mã hoá b theo cách nào
đó. Dạng đã mã hoá của b đôI khi đợc gọi blob và phơng pháp mã hoá
đợc gọi là một sơ đồ cam kết bít. Nói chung , một sơ đồ cam kết bít là một
hàm f: {0,1} x X Y, trong đó X và Y là các tập hữu hạn. Một phép mã hoá
của b là giá trị bất kỳ f(b,x), xX. Ta có thể định nghĩa một cách phi hình
thức hai tính chất mà một sơ đồ cam kết phải thoả mãn .

Tính chất giấu kín:
Với một bít b = 0 hoặc 1, Vic không thể xác định đợc giá trị
của b từ blob f(b,x).
Tính ràng buộc :

Sau đó Peggy có thể mở đợc blob bằng cách tiết lộ giá trị x
dùng mã hoá b để thuyết phục Vic rằng b là giá trị đã mã.
Peggy không thể mở một blob bởi cả hai giá trị 0 và 1.

Nếu Peggy muốm cam kết ( ràng buộc) một xâu bit bất kỳ thì một cách
đơn giản là cô ta phảI ràng buộc từng bit một cách độc lập .

Một phơng pháp để thực hiện cam kết bit là sử dụng hệ mật xác suất
Goldwasser - micali mô tả ở phần 12.4 hãy nhớ lại rằng trong hệ mật này n =
pq trong đó p, q là các số nguyên tố và m ???QR(n). Các số nguyên m và

x
2
2
(mod n)
Với các giá trị x
1
, x
2
nào đó thuộc Zn. Tuy nhiên
Vietebooks Nguyn Hong Cng
Trang 19
m (x
2
x
1
-1
)
2
mod n
điều này mâu thuẫn bởi vì m ??????QR(n)
Các sơ đồ ràng buộc bit sẽ đợc dùng để xây dựng các phép chứng
minh không tiết lộ thông tin. Tuy nhiên chúng còn có một ứng dụng tuyết vời
khác vào một bái toán tung đồng xu qua đIện thoại. Giả sử Alice và Bob
muốn đa ra một quyết định nào đó dựa trên phép tung đồng xu ngẫu nhiên
nhng họ không ở cùng một địa đIểm .ĐIều này có nghĩa là không thể thực
hiện đợc công việc một ngời tung đồng xu thực còn ngời kia kiểm tra
phép thử này. Sơ đồ ràng buộc bit sẽ cho một phơng pháp thoát khỏi tình
trạng bế tắc này. Một trong hai ngời ( chẳng hạn Alice ) sẽ chọn một bit
ngẫu nhiên b và tính blob y .Cô ta sẽ trao y cho Bob. Bây giờ Bob sẽ giả định
giá trị của b và rồi Alice sẽ mở blob để tiết lộ b. ở đây, tính chất giấu kín có



=
b SLB(x) Nếu pmod
b SLB(x) Nếu pmod
x)f(b,
1-p
x

=
=
Vietebooks Nguyn Hong Cng
Trang 20
Sơ đồ thoả mãn tính ràng buộc và theo các nhận xét đã nêu, nó cũng
thoả mãn tính giấu kín nếu bái toán logarit rời rạc trong Z
p
là không giảI đợc
. 13.4 .các chứng minh không tiết lộ thông tin về mặt
tính toán .

Trong phần này ta sẽ đa ra một hệ thống chứng minh không tiết lộ thông
tin cho bái toán quyết định NP đầy đủ là bái toán về khả năng tô màu một đồ
thị bằng ba màu, bái toán này đợc nêu ở hình 13.11.