Bài giảng Chứng minh không tiết lộ thông tin

Trường Đại học Dân lập Hải PhòngBỘ MÔN CÔNG NGHỆ THÔNG TIN   Chứng minh không tiết lộ thông tin ( Zero-knowledge proofs) Giảng viên: KS Trần Ngọc Thái Sinh viên thực hiện: Nguyễn Thế Tân Lê Quang Đức Tổng quan: Chứng minh không tiết lộ thông tin là gì? Giới thiệu những sự chứng minh tương tác Định nghĩa Chứng minh không tiết lộ thông tin. Các thuộc tính của chứng minh không tiêt lộ thông tin. Ứng dụng của Chứng minh không tiết lộ thông tin: Giao thức xác minh Feige-Fiat-Shamir. Giao thức xác minh Schnorr’s. Kết luận. Zero Knowledge Proof là gì? Ví dụ đơn giản: Hang động của Ali Baba. Alice muốn chứng minh cho Bob là anh ta biết cách mở cánh cửa bí mật giữa R và S. Bob đi tới P Alice đi tới R hoặc S Bob đi tới Q và bảo Alice đi tới đó từ cửa khác của hang động. Nếu Alice biết được bí mật thì lần nào anh ta cũng xuất hiện từ cửa đúng của hang. Bob lặp lại nhiều lần cho đến khi anh ta tin rằng Alice có thể mở cánh cửa bí mật. Image from RSA Labs [1] Giới thiệu về sự chứng minh tương tác: Prover (P) thử chứng minh một vài sự thật để kiểm chứng. Verifier (V) chấp nhận hoặc bác bỏ sự chứng minh của Prover. Chứng minh sẽ thuyết phục Verifier về một sự khẳng định nào đó: Chứng minh rằng anh ta biết một giá trị bí mật s. Vài party khác trong giao thức được đề cập dưới đây: Nhận một thông điệp từ một party khác Thực hiện một sự tính toán riêng. Gửi thông điệp cho một party khác. Lặp t lần quá trình đó. Interactive Proof Protocol Prover and verifier chia sẻ các đầu vào phổ biến (Các hàm hoặc giá trị) Giao thức trả về Accept cho mỗi trả lời được chấp nhận bởi Verifier. Ngược lại, Giao thức trả về Reject Các thuộc tính của Sự chứng minh tương tác: Sự hoàn thành: Verifier chấp nhận sự chứng minh nếu sự kiểm chứng là True. Giả định: các Party tuân theo Giao thức. Tính vững chắc: Nếu thực tế là FALSE, Verifier sẽ từ chối sự chứng minh Giả định: các Party tuân theo Giao thức. Sự chứng minh tương tác – Tính vững chắc và sự hoàn thành: Sự hoàn thành: Prob[(P,V)(x) = Accept | x Î L] ≥ ε Tính vững chắc: Prob[(¬P,V)(x) = Accept | x Ï L] ≤ δ Với: ε Î (½,1] δ Î [0,½) L là nhận các giá trị {0,1} (P,V) là một giao thức chứng minh tương tác bao gồm P và V Chứnh minh không tiết lộ thông tin: Các trường hợp của chứng minh tương tác với các thuộc tính kéo theo: Sự hoàn thành – Các định lý đúng có thể chứng minh. Tính bền vững – Các định lý sai không có khả năng chứng minh. Không có thông tin riêng nào của Prover được tiết lộ với Verifier – thuộc tính không công khai của zero-knowledge. Thuộc tính Zero Knowledge: Một bản ghi được chọn của các thông điệp đưa ra kết qủa từ giao thức thực thi Random1,Challenge1,Response1,Random2,Challenge2,Response2, … , Randomm,Challengem,Responsem Một simulator là một giải thuật thời gian đa thức phát hiện các bản ghi sai(không có prover) được xác thực là chính xác. Random1,Challenge1,Response1,Random2,Challenge2,Response2, … , Randomm,Challengem,Responsem Sự chứng minh tương tác có thuộc tính zero knowledge nếu một simulator tồn tại cho chứng minh. Lược đồ xác minh: Quy định cách thức chứng minh bạn là ai: Đưa ra cho bạn một giá trị bí mật mà không bộc lộ nó. Chứng minh tính xác minh Feige-Fiat-Shamir Giao thức xác minh Schnorr’s. Giả thuyết zero knowledge được sử dụng cho tất cả PKIs( Public-key infrastructure-cơ sở hạ tầng khóa công khai) Bạn không được tiết lộ khóa riêng của mình Tuy nhiên phần lớn PKIs chỉ là một quá trình đơn. Giao thức xác minh Feige-Fiat-Shamir Một chứng thực đáng tin cậy được công bố là trị tuyệt đối của n tức là tích của 2 primes lớn nhất Các số nguyên tố của mẫu 4r+3 (Blum nguyên) Chỉ những kết quả tin cậy được xác nhận. Với Ā là Prover và B Verifier Giao thức xác minh Feige-Fiat-Shamir Để Ā chứng minh nó xác minh với B, giao thức sau đây được thực thi Giao thức xác minh Schnorr’s Hai số nguyên tố p và q như là q|p-1 Thông thường |p| = 1024 và |q| = 160 g bằng orderp(g) = q y bằng y = g-a (mod p) Alice chọn một giá trị a sao cho a < q Khóa dùng chung của Alice là (p, q, q, y) được chứng nhận bởi CA. Giao thức xác minh của Schnorr Bob biết Alice có một vài aÎZq với y ≡ g-a (mod p) Để chứng minh cho Bob, các bước sau đươc lặp log2log2p lần Alice chọn k ÎuZq và tính gk (mod p) mà cô ta gửi cho Bob Bob chọn x Îu {0,1}log2log2p và gửi cho Alice Alice tính y = k + ax (mod q) Bob kiểm tra gk (mod p) ≡ gxgy Nhận xét: Trường hợp đặc biệt của chứng minh tương tác. Zero knowledge proofs cung cấp một cách chứng minh tri thức cho một ai đó mà không thay đổi bất cứ kiến thức bổ sung cho người đó Có thể được dùng để chứng minh sự xác minh. Giả thuyết cơ bản được dung trong tất cả PKIs References O. Goldreich. Foundations of Cryptography: Basic Tools. USA: Cambridge Press, 2001. D. R. Stinson. Cryptography: Theory and Practice (1st edition). Boca Raton: CRC Press, 1995. W. Mao. Modern Cryptography: Theory and Practice. New Jersey: Prentice Hall, 2003. A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. Boca Raton: CRC Press, 1996. L. Guillou, and J.J. Quisquater. “How to Explain Zero-Knowledge Protocols to Your Children”. Advances in Cryptology, CRYPTO 1989. G. Simari. “A Primer on Zero Knowledge Protocols”. M. Tompa. “Zero knowledge interactive proofs of knowledge (a digest)”. Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, 1988. U. Feige, A. Fiat, and A. Shamir. “Zero-knowledge proofs of identity”. ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), 1987. RSA Laboratories, “What are interactive proofs and zero-knowledge proofs?” Question ??? “ Tri thức phải đến thông qua hành động; bạn không thể có sự thử nghiệm nào mà không có ý tưởng; và đúc rút bằng thử nghiệm.” ~ Sophocles