CHƯƠNG 1: GIAO THỨC ĐỊNH DANH TRI THỨC KHÔNG 1.1 Giới thiệu về giao thức tri thức không 1.1 Khái niệm Trong bối cảnh hiện nay, việc trao đổi dữ liệu là hoạt động xảy ra liên tục và thường xuyên trong các dữ liệu đó chứa các dữ liệu, thông tin quan trọng nếu để lộ lọt có thể gây ra những hậu quả xấu về sau. Ví dụ như số thẻ tín dụng hoặc mật khẩu để truy cập cơ sở dữ liệu bí mật. Một bên thứ ba có thể nghe lén việc truyền nhận dữ liệu và sau đó sử dụng dữ liệu theo một cách nào đó phục vụ cho lợi ích cá nhân của kẻ đó. Trong thực tế đã xảy ra các hành vi như chặn các tin nhắn thanh toán điện tử và sau đó sử dụng thông tin đã đánh cắp được chiếm đoạt số tiền.
Độ an toàn của hệ mật chủ yếu dựa trên tính bí mật của khóa. Trong hệ mật khóa bí mật, hai bên đều thống nhất về một khóa bí mật chung trước khi bất kỳ trao đổi nào có thể xảy ra. Trong hệ mật khóa công khai, mỗi bên có một cặp khóa, một khóa được công khai có sẵn cho mọi người và 1 khóa được giữ bí mật. Việc này giúp loại bỏ sự cần thiết phải có sự thống nhất từ trước giữa hai bên.
Độ mạnh của hệ mật khóa công khai dựa trên các tài nguyên tính toán hạn chế có sẵn của mỗi người dùng, kể cả người sử dụng hợp pháp lẫn kẻ nghe lén bất hợp pháp. Ý tưởng chính trong bất kỳ hệ mật khóa công khai nào là một bài toán khó giải trong một thời gian ngắn. Ở hệ mật khóa công khai có hai khóa đó là khóa riêng và khóa chung. Với khóa chung, người dùng có thể mã hóa tin nhắn và người khác có thể giải mã chúng bằng khóa riêng.
Chủ sở hữu khóa riêng sẽ là người duy nhất có thể giải mã các tin nhắn, bất kỳ ai biết khóa chung đều có thể truyền thông tin một cách riêng tư. Ý tưởng chứng minh kiến thức về dữ liệu mà không tiết lộ bất kỳ thông tin nào về chính dữ liệu đó là rất hấp dẫn. Giao thức tri thức không cho phép loại kịch bản này diễn ra. Chúng là các giao thức mật mã không tiết lộ bí mật trong quá trình hoạt động, vì bí mật không được chuyển cho bên kia, nhưng người dùng vẫn có thể chứng minh cho bên kia rằng mình biết bí mật đó.
Cách tiếp cận này có thể là một giải pháp tốt để chứng minh danh tính lẫn nhau hoặc ví dụ trong bước trao đổi khóa của ứng dụng mật mã. Trong các giao thức tri thức không, một người chứng minh (Prover) cố gắng chứng minh kiến thức về một bí mật đối với người xác minh (Verifier) mà không tiết lộ bí mật đó. Người xác minh có thể đặt câu hỏi với mục tiêu rằng tìm hiểu xem người chứng minh (Prover) có thực sự biết bí mật hay không, nhưng anh ta không thể khám phá thông tin về bí mật. Một kẻ nghe lén là một bên thứ ba lắng nghe cuộc trò chuyện, nhưng nếu giao thức được bảo mật, anh ta không thể tìm hiểu bất cứ điều gì về bí mật hoặc thuyết phục người khác rằng anh ta biết bí mật được trao đổi.
Kỹ thuật này được gọi là “bằng chứng tri thức không” – ZKP. Tóm lại, bằng chứng tri thức không là một kỹ thuật để hạn chế lượng thông tin được truyền từ một người A sang người B. Để có thể hoạt động được bằng chứng tri thức không cần thoả mãn những tính chất sau: Completeness (tính đầy đủ): Nếu mệnh đề là đúng thì một người kiểm tra trung thực sẽ bị thuyết phục bởi một người chứng minh trung thực rằng mệnh đề đó là đúng. Soundness (tính tin cậy): Nếu người chứng minh là không trung thực thì họ không thể thuyết phục được người kiểm tra rằng mệnh đề đúng bằng cách dối trá.
Zero-Knowledge (tính tri thức không): Nếu mệnh đề là đúng thì người kiểm tra chỉ biết là nó đúng và không thể biết được chính xác mệnh đề đó là gì.2 Một số ví dụ về bằng chứng tri thức không 1.1 Mô hình hang động Hình 1.1 Mô hình hang động Đây là một cái hang hình tròn với một cánh cửa ngăn đôi ở cuối hang. Người chứng minh (P) sẽ chứng minh cho người xác minh (V) là mình biết mật khẩu mở cửa mà không cần nói cho (P) biết cụ thể mật khẩu là gì. Ta sẽ thực hiện việc này theo các bước sau: • (P) đi vào hang và chọn đi theo hướng A hoặc B tuỳ ý và đi đến chỗ cánh cửa. • (V) đi vào cửa hang và yêu cầu: "(P) hãy xuất hiện ở cửa B".
Khi đó sẽ có 2 trường hợp: - Nếu ban đầu (P) đi vào đường B thì (P) chỉ cần quay đầu trở lại. - Nếu ban đầu (P) đi vào đường A thì cách duy nhất để (P) có thể xuất hiện ở đầu B là (P) phải biết mật khẩu cửa để đi từ đầu A sang đầu B. • Giả sử là (P) xuất hiện ở đầu B thật, vậy ta sẽ có 50% xác xuất là (P) không biết mật khẩu cửa. Vậy là thế nào để ta có thể chắc chắn được (P) biết mật khẩu ? Đơn giản, ta hãy thực hiện việc kiểm tra này thật nhiều lần.
Nếu lần 2 (P) vẫn đúng thì xác suất đúng sẽ là: 0,5 × 0,5 = 0,25, lần 3 sẽ là 0,5 × 0,5 × 0,5 = 0,125 và cứ tiếp tục như vậy. Sau 100 lần chẳng hạn thì xác suất ăn may của (P) sẽ là cực kì nhỏ và lúc này, ta hầu như có thể chắc chắn là (P) biết mật khẩu cửa thực sự. Kiểm chứng lại ba tính chất của bằng chứng tri thức không: • Completeness (tính đầy đủ): Nếu (P) biết mật khẩu cửa thì (V) sẽ bị thuyết phục (bằng cách kiểm tra nhiều lần). • Soundness (tính tin cậy): Nếu (P) ăn may 1, 2 lần thì bằng cách thử lại nhiều lần, ta đã loại bỏ được khả năng này.
• Zero-Knowledge (tính tri thức không): (V) không hề biết thực sự mật khẩu là gì. Người mù màu với bóng đỏ và xanh Những người bị bệnh mù màu khi được đưa ra hai quả bóng có màu khác nhau thì với họ, họ cũng không thể phân biệt được. Vậy làm thế nào để một người bình thường (Prover) có thể chứng minh cho một người mù màu (Verifier) rằng họ biết là hai quả bóng khác màu mà không lộ ra là quả bóng nào là quả nào và có màu gì ? Các bước thực hiện như sau: • Người bị mù màu sẽ giấu hai quả bóng sau lưng, sau đó đưa ra một quả cho người bình thường xem. • Sau đó người bị mù màu sẽ giấu quả bóng vừa đưa ra về sau lưng, rồi đưa quả bóng còn lại (hoặc chính quả bóng vừa đưa ra) cho người bình thường xem và yêu cầu người bình thường trả lời là anh ta đã tráo quả bóng hay không.
• Lặp đi lặp lại việc này nhiều lần. Nếu người mù màu tráo bóng thì ta có thể nhận ra ngay bằng việc nhìn vào màu của chúng, nếu không thì có 50% xác suất là chúng ta đoán mò (bóng giống nhau nhưng chúng ta lại kêu là khác nhau). Tương tự như ví dụ trên, bằng cách lặp đi lặp lại nhiều lần, người bị mù màu có thể giảm xác suất này xuống và cuối cùng bị thuyết phục là người bình thường biết là hai quả bóng khác nhau. Các tính chất của bằng chứng tri thức không vẫn được đảm bảo.
• Completeness (tính đầy đủ): Người bình thường thuyết phục được người bị mù màu là hai quả bóng khác nhau. • Soundness (tính tin cậy): Người bình thường không thể đoán mò. • Zero-Knowledge (tính tri thức không): Người mù màu không biết quả bóng nào là quả nào và có màu gì.2 Cơ sở toán học của giao thức tri thức không 1.1 Khái niệm độ phức tạp của thuật toán 1.1 Khái niệm thuật toán Thuật toán là một thủ tục tính toán được định nghĩa hoàn toàn xác định, lấy các biến đầu vào và dừng lại cùng với đầu ra. Tất nhiên, thuật ngữ “thủ tục tính toán được định nghĩa hoàn toàn xác định” là không chính xác về mặt toán học.
Nó có thể chính xác hóa bằng cách sử dụng các mô hình tính toán hình thức như máy Turing, máy truy nhập ngẫu nhiên hoặc mạch boolean. Thay cho việc đi sâu vào bản chất kỹ thuật của các mô hình này, đơn giản hơn là nghĩ đến một thuật toán, ví dụ như chương trình máy tính được viết trong một ngôn ngữ lập trình cụ thể nào đấy, cho một máy tính nào đấy, lấy các biến đầu vào và dừng với đầu ra. Thời gian chạy của thuật toán trên một đầu vào cụ thể là số các phép toán cơ sở hoặc “các bước” được thực hiện. Thông thường các bước có nghĩa là các phép toán theo bit.
Đối với một số thuật toán, sẽ thuận tiện hơn khi lấy các bước là phép so sánh, lệnh máy, nhịp đồng hồ máy, phép nhân modulo,. Thời gian chạy trong trường hợp xấu nhất của thuật toán là cận trên về thời gian chạy cho đầu vào bất kỳ, được biểu diễn như là hàm số của đầu vào. Thời gian chạy trung bình của thuật toán là thời gian chạy trung bình trên tất cả các đầu vào có kích thước cố định, được biểu diễn như là hàm số của đầu vào.2 Độ phức tạp tính toán Độ an toàn của các hệ mật khóa công khai đều dựa trên độ phức tạp tính toán của các bài toán khó. Lý thuyết thuật toán và các hàm số tính được ra đời đã đặt nền móng cho việc nghiên cứu các vấn đề “tính được”, “giải được” trong toán học.
Tuy nhiên, từ vấn đề “tính được” một cách trừu tượng, hiểu theo nghĩa tiềm năng đến việc tính được trong thực tế của khoa học tính toán bằng máy tính điện tử là cả một khoảng cách rất lớn. Đã có rất nhiều bài toán được chứng minh là tính được một cách tiềm năng nhưng không tính được trong thực tế, dù có sự hỗ trợ của máy tính điện tử. Mục đích chính của lý thuyết độ phức tạp là cung cấp các cơ chế để phân loại các bài toán tính toán theo các tài nguyên được yêu cầu để giải chúng. Thông thường, khó có thể nhận được chính xác thời gian chạy của thuật toán.
Trong trường hợp như vậy buộc phải dựa vào việc xấp xỉ thời gian chạy và thông thường kết quả nhận được là thời gian chạy tiệm cận. Thuật toán thời gian đa thức là thuật toán có hàm thời gian chạy trong trường hợp tồi nhất là O(n k ) , với n là kích thước đầu vào và k là hằng số.