Zero knowledge và ứng dụng trong an toàn dữ liệu.

- Sự hướng dẫn của thầy đã giúp tôi có thêm được những hiểu biết về một số vấn đề liên quan đến bảo mật thông tin.
- Hà Nội, tháng 10 năm 2014 HỌC VIÊN THỰC HIỆN Bùi Xuân Bình 4 DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT Ký hiệu, viết tắt Giải thích CT Cử tri ƯCLN Ước chung lớn nhất gcd(m, n) Uớc chung lớn nhất của m và n KP Kiểm phiếu TT Trung thực CM KTLTT Chứng minh không tiết lộ thông tin TMĐT Thương mại điện tử TTĐT Thanh toán điện tử Prover Người chứng minh Verifier Người xác minh 5 DANH MỤC CÁC BẢNG Bảng 2.1.
- Quá trình chứng minh đại diện tài khoản Bảng 3.2.
- Giao thức rút tiền Bảng 3.3.
- Giao thức thanh toán Bảng 3.4.
- Giai đoạn 1 Cử tri chứng minh lá phiếu hợp lệ Bảng 3.5.
- Giai đoạn 2 Người xác minh TT chứng minh lá phiếu làm mù hợp lệ......74 Bảng 3.6.
- Sơ đồ chứng minh tương tác Hình 3.1.
- Sơ đồ giao thức Fiat – Shamir Hình 3.2.
- Sơ đồ giao thức Feige-Fiat-Shamir Hình 3.3.
- ZERO KNOWLEDGE .
- Chứng minh tương tác .
- Khái niệm .
- Chứng minh không tiết lộ thông tin .
- Giao thức .
- Các thành phần trong phép chứng minh không tiết lộ thông tin .
- Hệ thống CM KTLTT cho tính Đẳng cấu của đồ thị .
- Khái niệm đồ thị đẳng cấu .
- Sơ đồ chứng minh .
- Chứng minh sơ đồ có tính đầy đủ Chương 2: CƠ SỞ MẬT MÃ .
- Giao thức xác thực không lộ .
- Giao thức xác thực Fiat-Shamir .
- Giao thức xác thực Feige-Fiat-Shamir .
- Giao thức xác minh Schnorr’s .
- Chứng minh tính hợp lệ của lá phiếu (x, y) (Giao thức .
- Chứng minh quyền sở hữu giá trị bí mật β (Giao thức .
- Mã nguồn chương trình MỞ ĐẦU Ngày nay, công nghệ thông tin đã và đang phát triển mạnh mẽ, Internet đã trở thành một phần không thể thiếu trong cuộc sống hàng ngày thì các hoạt động trao đổi thông tin, giao dịch điện tử,…trên môi trường mạng diễn ra thường xuyên và ngày càng phổ biến hơn.
- Chính vì vậy mà việc bảo mật, đảm bảo an toàn thông tin đang là nhu cầu cấp thiết.
- Trước các nhu cầu cấp thiết đó, lý thuyết về mật mã thông tin đã ra đời nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như khi dữ liệu đang được truyền trên mạng.
- THỬ NGHIỆM CHƯƠNG TRÌNH “Chứng minh không để lộ thông tin”, là phương pháp chứng minh không có nghĩa là “không để lộ thông tin” mà là “để lộ thông tin ở mức ít nhất” về sự vật, sự việc cần chứng minh.
- Với việc “không để lộ” người xác minh sẽ không có nhiều hiểu biết về sự vật, sự việc, họ chỉ thu được chút ít thông tin (coi như là không) về đặc điểm tính chất của nó.
- Ngành mật mã học luôn phát triển không ngừng, trong phạm vi khóa luận này, chúng tôi chỉ trình bày một vấn đề là phương pháp “chứng minh không tiết lộ thông tin” đồng thời tìm hiểu một số ứng dụng thực tế của cơ sở lý thuyết này.
- ZERO KNOWLEDGE 1.1.
- Chứng minh tương tác 1.1.1.
- Khái niệm Trước tiên ta thảo luận ý tưởng về hệ thống chứng minh tương tác.
- Trong hệ thống chứng minh tương tác có hai thành viên: Alice và Bob.
- Alice là người chứng minh và Bob là người kiểm tra phép chứng minh.
- Alice biết một điều bí mật gì đó và cô ta muốn chứng minh cho Bob rằng cô ta biết điều đó.
- Sơ đồ chứng minh tương tác (Hình 1) Phép chứng minh tương tác là một giao thức hỏi đáp, gồm một số vòng xác định.
- Một vòng của giao thức gồm một yêu cầu của Bob và một đáp ứng của Alice.
- Tới cuối phép chứng minh, Bob sẽ chấp nhận hoặc từ chối phép chứng minh của Alice tùy thuộc vào việc liệu Alice có đáp ứng thành công các yêu cầu của Bob hay không.
- Các tính chất Sự chứng minh tương tác có 2 tính chất, Sự hoàn thành và Tính chắc chắn.
- Một sự chứng minh tương tác được thừa nhận là Complete nếu Verifier chấp nhận sự chứng minh đưa ra là True.
- Nói cách khác, vài định lý đúng được chứng minh.
- 10 Ví dụ, nếu một Prover nói rằng anh ta biết một giá trị bí mật, và kiểm chứng là đúng, anh ta có thể chứng minh nó với Verifier.
- Sau đó, sự chứng minh tương tác có thể nói rằng Hoàn thành.
- Tính chất chắc chắn - khẳng định rằng một Verifier sự chứng minh nếu thực tế nó sai.
- Nghĩa là, không một định lý sai nào có thể được chứng minh.
- Trong cả 2 trường hợp giả định là Prover và Verifier tuân theo Giao thức.
- Chúng không tương tác với các Party khác và cố hiểu thông tin theo một nghĩa khác.
- Phép chứng minh tương tác có thể thực hiện được trong thời gian đa thức gọi là phép chứng minh tương tác trong thời gian đa thức.
- Minh họa hoạt động của giao thức tương tác để chứng minh sự đẳng cấu của hai đồ thị.
- Giả sử G1 = {V, E1} và G2 = {V, E2 } là hai đồ thị với tập đỉnh V và các tập cạnh E và E .
- Giả sử Alice biết G2 đẳng cấu với G1 qua hoán vị.
- Một vòng của giao thức có thể xảy ra như sau.
- Alice chọn ngẫu nhiên một hoán vị.
- {2 4 1 3} đồ thị H sẽ có tập cạnh là ảnh của G1 qua.
- Toàn bộ giao thức gồm có m = log2n vòng.
- Chứng minh không tiết lộ thông tin 1.2.1.
- Khái niệm Nói một cách đơn giản, hệ thống chứng minh không tiết lộ thông tin cho phép một đối tượng thuyết phục một đối tượng khác tin vào một điều gì đó (chứng minh) mà vẫn không để lộ phương pháp chứng minh (không tiết lộ thông tin).
- V yêu cầu P chứng minh điều này.
- Có một cách khác để P chứng minh rằng 2 quân bài đó là “át” và “2”, mà không phải lật 2 quân bài đó lên, tức là không làm lộ thông tin về 2 quân bài trên tay P.
- Qua ví dụ trên có thể tạm hiểu “Chứng minh không tiết lộ thông tin” không có nghĩa là “không để lộ thông tin”, mà có nghĩa là “để lộ thông tin ở mức ít nhất” về sự vật, sự việc cần chứng minh.
- Với những “thông tin để lộ”, người xác minh không có đầy đủ hiểu biết (knowledge) về sự vật, sự việc, họ chỉ thu được rất ít thông tin (coi như “zero knowledge”) về đặc điểm tính chất của nó.
- 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.
- 12  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.
- Giao thức  Giao thức  là giao thức “Hỏi - Đáp” 3 bước, để P chứng minh cho V một vấn đề nào đó.
- Kết quả V thừa nhận hoặc bác bỏ vấn đề P chứng minh.
- “Chứng minh không tiết lộ thông tin” được phát minh bởi Goldwasser, Micali và Rackoff năm 1981 (được viết tắt là GMR).
- Chứng minh không tiết lộ thông tin (và chứng minh tương tác) là một trong những lý thuyết hay và có ảnh hưởng lớn trong khoa học máy tính.
- Các thành phần trong phép chứng minh không tiết lộ thông tin Có hai nhân vật mà chúng ta thường xuyên nhắc đến trong vấn đề này.
- Peggy Prover (người chứng minh): Peggy có thông tin muốn chứng minh cho Victor thấy, nhưng cô ấy lại không muốn nói thẳng bí mật đó cho Victor.
- Victor không thu được điều gì từ bí mật đó, ngay cả khi anh ta gian lận hay không tuân theo chỉ dẫn của giao thức.
- Hệ thống CM KTLTT cho tính Đẳng cấu của đồ thị 1.3.1.
- Khái niệm đồ thị đẳng cấu + Khái niệm : Bài toán đồ thị đẳng cấu được mô tả dưới đây.
- Đồ thị đẳng cấu 13 Cho 2 đồ thị n đỉnh G1 = (V1, E1) và G2 = (V2, E2), G1 và G2 được đẳng cấu nếu có một song ánh p: V1 V2 sao cho {u,v.
- Một sơ đồ chứng minh tương hỗ cho tính đẳng cấu của đồ thị Sơ đồ nêu ra dưới đây nhằm thực hiện mục đích: Lan muốn thuyết phục Nam rằng hai đồ thị đã cho là đẳng cấu bằng một giao thức chứng minh tương hỗ, nhưng vào lúc kết thúc giao thức Nam vẫn không có chút thông tin nào về cách chứng minh (cho chính anh ta hoặc chứng minh cho người thứ 3) rằng hai đồ thị đó là đẳng cấu.
- Đây là một khái niệm rất khó định nghĩa hình thức, vì vậy ta sẽ xét một ví dụ trước khi định nghĩa Hệ thống CMKTLTT hoàn thiện cho tính đẳng cấu của đồ thị: Đầu vào: Thông tin công khai: Hai đồ thị G1 và G2, mỗi đồ thị có tập đỉnh {1…n}.
- Thông tin bí mật của Lan: Phép hoán vị σ đưa G2 trở thành G1.
- Lan chọn một phép hoán vị ngẫu nhiên  của {1…n} cô ta tính H là ảnh của G1 theo  và gửi H cho Nam.
- Kết thúc: Nam sẽ chỉ chấp nhận chứng minh của Lan, nếu H là ảnh của Gi ở mỗi một trong n vòng.
- Một phép đẳng cấu từ G2 sang G1 là hoán vị σ .
- Tính chất Dễ dàng kiểm tra được tính đầy đủ và tính đúng đắn của giao thức.
- Không khó khăn thấy rằng, xác suất để Nam chấp nhận sẽ bằng 1 nếu Lan biết phép chứng minh G1 đẳng cấu với G2.
- Ngược lại, nếu Lan không biết phép chứng minh thì chỉ có một cách để Lan lừa dối được Nam và cô ta phải giả định giá trị i mà Nam sẽ chọn ở mỗi vòng và truyền cho Nam một đồ thị ngẫu nhiên (đẳng cấu với Gi tương ứng).
- 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ù Nam đã thuyết phục rằng G1 là đẳng cấu với G2 nhưng anh ta vẫn không thu thêm được tý kiến thức nào để giúp tìm được phép hoán vị σ đưa G2 về G1.
- Tất cả những điều mà Nam thấy trong mỗi vòng của phép chứng minh là một đồ thị ngẫu nhiên H đẳng cấu với các đồ thị G1 và G2 cùng với một phép hoán vị đưa G1 thành H hoặc đưa G2 thành H (nhưng không phải là cả hai).
- Tuy nhiên, Nam có thể tự mình tính các bản sao ngẫu nhiên của các đồ thị này mà không cần tới sự giúp đỡ của Lan.
- Vì các đồ thị H được chọn một cách độc lập và ngẫu nhiên ở mỗi phần của phép chứng minh nên điều này không giúp đỡ được gì cho Nam trong việc tìm một phép đẳng cấu từ G1 sang G2.
- 15 Ta xem xét kĩ lưỡng thông tin mà Nam thu được nhờ tham gia vào hệ thống chứng minh tương hỗ.
- Các đồ thị G1 và G2.
- Bởi vậy, các thông tin T thu được qua sơ đồ chứng minh tương hỗ về phép đẳng cấu đồ thị sẽ có dạng sau: T = ((G1, G2).
- Giả mạo biên bản ghi nhận được sau giao thức chứng minh Đ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à Nam (hay bất kì người nào khác) có thể giả mạo các thông tin T (mà không cần phải tham gia vào hệ thống chứng minh tương hỗ) giống như các thông tin thực tế.
- Việc giả mạo được thực hiện theo thuật toán được mô tả như sau: Thuật toán giả mạo chứng minh tương hỗ cho tính đẳng cấu: Đầu vào: Hai đồ thị G1 và G2, mỗi đồ thị có tập đỉnh {1…n} Thuật toán: T = (G1, G2) For j = 1 to n do Chọn ngẫu nhiên ij =1 hoặc 2 Chọn j là một hoán vị ngẫu nhiên của {1,…,n} Tính Hj là ảnh của Gij theo j Ghép (Hj, ij, j) vào cuối của T.
- Theo ngôn ngữ của phép chứng minh không tiết lộ thông tin, một thuật toán giả mạo thường được gọi là một bộ mô phỏng.
- Bởi vậy, việc tham gia vào hệ thống chứng minh sẽ không làm tăng khả năng tính toán của Nam

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt