Thực đơn
trang chủĐiện thoại

Bằng chứng không có kiến ​​thức. Một thí nghiệm tưởng tượng với cỗ máy thời gian. Được rồi, vậy tất cả điều này có nghĩa là gì?

Sử dụng chứng minh với không có kiến ​​thức thông tin bí mật có thể được giải thích bằng một ví dụ cụ thể. Giả sử có một cái hang. Cửa hang nằm ở điểm A, còn tại điểm B hang động chia thành hai nửa C và D. Hang động có một bí mật: chỉ những người biết mới biết từ kỳ diệu, có thể mở được cánh cửa nằm giữa C và D.

Anton biết những lời kỳ diệu, Boris thì không. Anton muốn chứng minh cho Boris thấy rằng anh ấy biết những từ kỳ diệu, nhưng theo cách mà Boris vẫn mù mờ về những từ này. Sau đó Anton có thể sử dụng giao thức sau:

1. Boris đang đứng ở điểm A.

2. Theo lựa chọn của mình, Anton tiến tới cửa từ điểm C,

hoặc từ điểm D.

3. Boris di chuyển đến điểm B.

4. Boris ra lệnh cho Anton xuất hiện qua lối đi bên trái tới cửa,

hoặc thông qua bên phải.

5. Anton tuân theo mệnh lệnh của Boris, nếu cần thiết hãy sử dụng

những lời kỳ diệu để vượt qua cánh cửa.

6. Các bước 1-5 được lặp lại n lần, trong đó n là tham số giao thức.

Giả sử rằng Boris có một chiếc máy quay video để ghi lại tất cả những lần Anton biến mất ở sâu trong hang động và tất cả những lần xuất hiện sau đó của anh ta. Nếu Boris đưa ra hồ sơ về tất cả n thí nghiệm mà anh ấy đã thực hiện cùng với Anton, liệu những hồ sơ này có thể dùng làm bằng chứng cho thấy Anton biết những từ ma thuật cho người khác (ví dụ: đối với Vladimir) không?

Khắc nghiệt. Vladimir sẽ không bao giờ có thể đảm bảo rằng Anton không thông báo trước cho Boris về ý định của anh ta mỗi lần, để rồi Boris sẽ ra lệnh cho anh ta rời đi chính xác từ phía cánh cửa mà Anton đã bước vào. Hoặc mọi thứ trong quá trình quay video không bị cắt bỏ thí nghiệm thất bại, trong thời gian đó Anton không thể thực hiện mệnh lệnh của Boris.

Điều này có nghĩa là Boris không thể thuyết phục Vladimir, người không đích thân có mặt trong các thí nghiệm trong hang động, rằng Anton thực sự đã xác nhận kiến ​​thức của mình về bí mật. Điều này có nghĩa là giao thức chứng minh mà Anton sử dụng có đặc điểm chính xác là không tiết lộ thông tin bí mật. Nếu Anton không biết những lời thần kỳ mở cánh cửa trong hang, thì khi quan sát Anton, Boris sẽ không thể phát hiện ra điều gì. Nếu Anton biết những lời kỳ diệu, thì ngay cả một đoạn video ghi lại chi tiết các thí nghiệm đã thực hiện cũng không giúp ích được gì cho Boris. Thứ nhất, vì khi xem, Boris sẽ chỉ nhìn thấy những gì mình đã xem trực tiếp. Và thứ hai, vì gần như không thể phân biệt được đoạn video do Boris làm giả với video thật.

Giao thức chứng minh không có kiến ​​thức hoạt động do thực tế là nếu không biết các từ ma thuật, Anton chỉ có thể thoát ra từ phía mà anh ta đã bước vào. Vì vậy, chỉ trong 50% tất cả các trường hợp Anton có thể đánh lừa Boris bằng cách đoán xem anh ta sẽ yêu cầu anh ta rời đi từ phía nào. Nếu số lượng thí nghiệm là n thì Anton sẽ vượt qua thành công tất cả các bài kiểm tra chỉ trong một trường hợp trong số 2 n. Trong thực tế, bạn có thể giới hạn bản thân ở mức n=16. Nếu Anton thực hiện đúng mệnh lệnh của Boris trong cả 16 trường hợp thì anh ấy thực sự biết được bí mật của lời nói thần kỳ.

Ví dụ về hang động chỉ mang tính minh họa nhưng có một sai sót đáng kể. Boris sẽ dễ dàng hơn nhiều khi thấy tại điểm B Anton rẽ theo một hướng và sau đó xuất hiện từ phía đối diện. Một giao thức chứng minh không có kiến ​​thức đơn giản là không cần thiết ở đây.

Do đó, hãy giả sử rằng Anton không biết một số từ thần kỳ, chẳng hạn như “Open Sesame”. Không, Anton có nhiều thông tin thú vị hơn - anh ấy là người đầu tiên tìm ra giải pháp cho vấn đề khó khăn này. Để chứng minh sự thật này Boris và Anton không cần phải chứng minh quyết định của mình với mọi người. Tất cả những gì anh ta cần làm là áp dụng giao thức chứng minh không có kiến ​​thức sau đây đối với thông tin bí mật:

1. Anton sử dụng thông tin anh ấy có và thông tin được tạo

số ngẫu nhiên để biến một bài toán khó thành một bài toán khó khác đẳng cấu vấn đề ban đầu. Anton sau đó giải quyết vấn đề mới này.

2. Anton sử dụng giao thức dự đoán bit cho bit được tìm thấy trên

bước 1 của quyết định, để sau này, nếu Boris cần làm quen với quyết định này, Boris có thể xác minh một cách đáng tin cậy rằng quyết định do Anton đưa ra đã thực sự được anh ấy nhận được ở bước 1.

3. Anton chỉ cho Boris một vấn đề khó khăn mới,

4. Boris yêu cầu Anton chứng minh hai bài toán khó

(cũ và mới) là đẳng cấu hoặc đưa ra lời giải mà lẽ ra Anton phải tìm ra ở bước 1 và chứng minh rằng đó thực sự là lời giải cho bài toán mà Anton đã rút gọn bài toán ban đầu trong cùng bước đó.

5. Anton đáp ứng yêu cầu của Boris.

6. Anton và Boris lặp lại các bước 1-6 n lần, trong đó n là tham số

giao thức.

Các bài toán khó giải, phương pháp quy đổi bài toán này sang bài toán khác, cũng như các số ngẫu nhiên, nếu có thể, nên chọn sao cho Boris không có bất kỳ thông tin nào về lời giải của bài toán ban đầu ngay cả sau khi lặp lại các bước của bài toán. giao thức.

Không phải tất cả các vấn đề khó giải quyết đều có thể được sử dụng trong các bằng chứng không có kiến ​​thức về thông tin bí mật, nhưng hầu hết chúng đều khá phù hợp cho các mục đích như vậy. Các ví dụ bao gồm tìm chu trình Hamilton (một đường kín đi qua tất cả các đỉnh của đồ thị chỉ một lần) trong một đồ thị được kết nối và xác định sự đẳng cấu của đồ thị (hai đồ thị là đẳng cấu nếu chúng chỉ khác nhau ở tên các đỉnh của chúng).

Bằng chứng không có kiến ​​thức sau lượng tử– các giao thức chứng minh không có kiến ​​thức có khả năng kháng lượng tử.

Các hệ thống/giao thức kháng lượng tử được coi là những hệ thống/giao thức không thể bị xâm phạm khi sử dụng sức mạnh tính toán Máy tính lượng tử. Thuật ngữ ổn định lượng tử được giới thiệu trong mật mã hậu lượng tử.

Nội dung

Tuyên bố về vấn đề an toàn thông tin

Máy tính lượng tử có sức mạnh tính toán tuyệt vời. TRÊN khoảnh khắc này Hướng này đang phát triển nhanh chóng. Với tất cả những điều này, việc tăng cường nghiên cứu trong lĩnh vực này (chắc chắn là một tính năng tích cực) làm giảm độ tin cậy của các hệ thống mật mã hiện đại đang được sử dụng, ví dụ như các hệ thống dựa trên việc nhân tử hóa các số nguyên hoặc các bài toán logarit rời rạc.

ZKBoo

ZKBoo dựa trên giao thức Điện toán bí mật (MPC). Ý tưởng của ZKBoo là thay thế MPC bằng cách phân rã (2,3) của chuỗi.

Chứng minh được xây dựng theo sơ đồ sau:

1) P tính f bằng cách sử dụng phân rã và nắm bắt 3 trạng thái;

2) P gửi các nghĩa vụ và đầu ra của từng trạng thái sau khi sử dụng phương pháp phỏng đoán FS;

3) Câu trả lời là 2 trong 3 trạng thái được mở cho mỗi lần phóng N;

4) V kiểm tra dữ liệu đầu ra xem đã hoàn tất quá trình khôi phục chưa; kiểm tra xem mỗi trạng thái trong số 2 trạng thái mở có được tính toán chính xác hay không và tính toán xem cuộc gọi có được tính toán chính xác hay không.

Số lần khởi chạy được chọn sao cho sai số không đáng kể, do đó khả năng kẻ tấn công thực hiện tất cả các lần khởi chạy là tối thiểu.

ZKB++

ZKB++ là phiên bản được sửa đổi ZKBoo.

1) Phân tách: trong View1 và View2, P phải bao gồm k(i) vì x(i) có thể được tính toán một cách xác định bởi V;

2) Không bao gồm dữ liệu đầu vào: các chia sẻ đầu vào được tạo giả ngẫu nhiên bằng cách sử dụng k(i) không cần được đưa vào biểu diễn khi e = 1. Dữ liệu chỉ cần được gửi nếu e = 2 hoặc e = 3, vì đối với trạng thái thứ ba, không thể lấy dữ liệu đầu vào từ dữ liệu ban đầu vì nó được tạo giả ngẫu nhiên bằng cách sử dụng k(i);

3) Không có nghĩa vụ gửi;

4) Không có trình tự ngẫu nhiên bổ sung cho các nghĩa vụ;

5) Không xem xét đầu ra: đầu ra có thể được tính toán từ phần còn lại của bằng chứng;

6) Không bao gồm biểu diễn trạng thái: V có thể tính toán lại trạng thái chỉ xem xét ngẫu nhiên k(e) và k(e+1).

Mạch ZKB++ hoàn chỉnh được hiển thị trong Hình 1.

Các cải tiến được thực hiện để tối ưu hóa ZKBoo giúp giảm kích thước bằng chứng xuống 2 lần cho ZKB++.

Thuật ngữ đẹp là một trong những lợi thế mật mã hiện đại. Tên ban nhạc Punk hoặc biệt danh Tumbl là những thuật ngữ mật mã như "vị ngữ cốt lõi", "chức năng cửa bẫy" hoặc "phân tích mật mã vi phân không thể" nghe giống như vậy). Đối với tôi, có vẻ như một thuật ngữ như " không có kiến ​​thức".

Nhưng vẻ đẹp của thuật ngữ “không có kiến ​​thức” đã dẫn đến việc lạm dụng nó. Mọi người ngay lập tức nghĩ rằng không có kiến ​​thức đang trở thành đồng nghĩa với “rất, rất an toàn”. Vì lý do này, những từ này được thêm vào tên của các hệ thống an ninh và mạng ẩn danh– điều này thực sự không liên quan gì đến giao thức không có kiến ​​thức.

Chúng tôi đã nói tất cả những điều này để nhấn mạnh điều chính: bằng chứng kiến ​​​​thức không là một trong những nhất công cụ mạnh mẽ mật mã từng phát triển. Nhưng thật không may, nó được nghiên cứu tương đối ít. Chúng ta hãy thử đưa ra một lời giải thích phi toán học về điều gì khiến ZK (không có kiến ​​thức) trở nên đặc biệt. Ở đây chúng ta sẽ nói về một số giao thức ZK hiện tại.

Nguồn gốc của kiến ​​thức không

Trước Goldwasser và những người khác, hầu hết công việc trong lĩnh vực này đều tập trung vào hệ thống chứng minh tính đúng đắn. Nghĩa là, trong trường hợp kẻ tấn công - Người kiểm tra - cố gắng đánh lừa Bộ điều khiển bằng cách đưa cho anh ta một giá trị sai. Nhưng Goldwasser, Micali và Rakoff lại nhìn vào mặt trái của vấn đề này. Thay vì chỉ lo lắng về Người kiểm tra, họ hỏi: điều gì sẽ xảy ra nếu bạn không tin tưởng Người kiểm soát?

Họ đặc biệt lo ngại về khả năng rò rỉ thông tin. Cụ thể, họ hỏi bao nhiêu thông tin thêm Kiểm soát viên sẽ nhận được gì trong quá trình chứng minh sự thật rằng tuyên bố đó là đúng?

Điều quan trọng cần lưu ý là đây không chỉ là mối quan tâm về mặt lý thuyết. Có thật ứng dụng thực tế, trong đó những điều này là quan trọng.

Đây là một trong số đó: hãy tưởng tượng rằng khách hàng đang ở trong thế giới thực muốn đăng nhập vào máy chủ web bằng mật khẩu. Cách tiếp cận tiêu chuẩnđến vấn đề "thế giới thực" liên quan đến việc lưu trữ phiên bản băm của mật khẩu trên máy chủ. Đăng nhập vào hệ thống như vậy được coi là một loại "xác nhận" rằng hàm băm của mật khẩu được cung cấp là đầu ra của hàm băm của mật khẩu hiện tại. Và quan trọng hơn, nó là “sự xác nhận” rằng khách hàng thực sự biết mật khẩu.

Hầu hết các hệ thống trong thế giới thực đều thực hiện "xác nhận" này theo cách tồi tệ nhất có thể. Máy khách chỉ cần chuyển mật khẩu ban đầu đến máy chủ, máy chủ sẽ tính toán lại hàm băm mật khẩu và so sánh nó với giá trị được lưu trữ. Vấn đề ở đây rất rõ ràng: máy chủ nhận được mật khẩu của tôi ở dạng hấp dẫn nhất đối với tin tặc, “văn bản thuần túy”. Và người dùng chỉ có thể cầu nguyện rằng bảo mật của máy chủ không bị xâm phạm.

Những gì Goldwasser, Micali và Rakoff đề xuất là niềm hy vọng về những phương pháp xác nhận mới. Nếu được triển khai đầy đủ, bằng chứng không có kiến ​​thức sẽ có thể cung cấp bằng chứng cho vấn đề được mô tả ở trên. Không tiết lộ một chút thông tin nào tương ứng với thực tế là “tuyên bố này là đúng”.

Ví dụ về "Thế giới thực"

Cho đến nay chúng ta đã nói về những điều khá trừu tượng. Hãy tiếp tục và mang theo ví dụ thực tế(hơi điên rồ) đối với giao thức không có kiến ​​thức.

Để giúp tôi giải thích ví dụ này, hãy giả sử rằng tôi là một ông trùm viễn thông và tôi đang trong quá trình triển khai một mạng di động mới. Của tôi cấu trúc mạngđược trình bày dưới đây trong biểu đồ này. Mỗi đỉnh của biểu đồ đại diện cho một máy phát di động và các đường kết nối (cạnh) hiển thị vị trí hai ô chồng lên nhau. Ở những vị trí này, các máy phát sẽ gây nhiễu lẫn nhau. Điều tốt là cấu trúc mạng của tôi cho phép mỗi tháp được cấu hình ở một trong ba dải tần để tránh ảnh hưởng như vậy.

Do đó, nhiệm vụ triển khai mạng của tôi là chỉ định làn đường riêng cho mỗi tháp sao cho các ô không giao nhau. Nếu sử dụng màu sắc để biểu thị các dải tần, chúng ta có thể nhanh chóng phát triển một giải pháp cho vấn đề này:


Tất nhiên, nhiều bạn đã nhận thấy. Những gì tôi mô tả ở đây chỉ là trương hợp đặc biệt vấn đề lý thuyết nổi tiếng. Nó được gọi là “bài toán tô màu đồ thị ba màu”. Bạn cũng có thể biết về một tính năng thú vị vấn đề này. Đối với một số đồ thị, rất khó tìm ra nghiệm hoặc thậm chí xác định rằng nghiệm đó có tồn tại hay không. Bài toán tô màu đồ thị bằng ba màu (và tìm câu trả lời cho câu hỏi liệu có lời giải như vậy cho trường hợp này), như đã biết, thuộc loại bài toán NP-đầy đủ.

Không cần phải nói rằng những câu đố về đồ chơi trên rất dễ giải. Nhưng nếu nó không dễ dàng như vậy thì sao? Ví dụ, hãy tưởng tượng rằng mạng của tôi thông tin di độngđã rất lớn và phức tạp. Trong trường hợp này, tôi sẽ không có đủ khả năng tính toán để tìm ra giải pháp. Trong trường hợp này, nên giao vấn đề cho người khác. Dành cho những người có đủ khả năng tính toán. Ví dụ: tôi có thể yêu cầu Google giải quyết vấn đề này.

Nhưng có một vấn đề.

Giả sử Google sẽ cung cấp cho tôi nhiều như tôi cần. khả năng tính toánđể tìm ra giải pháp tô màu chính xác cho biểu đồ của tôi. Tôi chắc chắn sẽ không trả tiền cho họ cho đến khi tôi chắc chắn rằng họ có giải pháp này. Đồng thời, Google sẽ không cung cấp cho tôi bản sao quyết định cho đến khi tôi thanh toán. Chúng ta đang ở ngõ cụt.

TRONG đời thực lẽ thường cho chúng ta biết câu trả lời cho vấn đề nan giải này liên quan đến luật sư và tài khoản ký quỹ. Nhưng ở đây chúng ta không nói về cuộc sống thực mà về mật mã. Và nếu bạn đã từng đọc tác phẩm của các nhà mật mã học, bạn cũng biết rằng cách duy nhất để tìm ra giải pháp cho một vấn đề là nghĩ ra một điều gì đó hoàn toàn điên rồ. giải pháp kỹ thuật. Giải pháp kỹ thuật điên rồ (có mũ)

Hãy tưởng tượng rằng các nhân viên của Google đã tham khảo ý kiến ​​của Silvio Micali từ MIT và anh ấy đã hỏi các đồng nghiệp của mình là Oded Goldreich và Avi Wigderson. Sau khi tham khảo ý kiến, họ đã phát triển một giao thức đẹp đến mức thậm chí không cần đến máy tính. Một nhà kho lớn với nguồn cung cấp bút chì màu và giấy sẽ được sử dụng. Bạn cũng sẽ cần một số lượng lớn mũ.

Hãy xem nó hoạt động như thế nào

Đầu tiên, tôi sẽ đi vào một không gian nhà kho và phủ giấy lên sàn để tạo không gian đại diện cho mạng di động của mình. Sau đó tôi sẽ rời khỏi nhà kho. Giờ đây, Google có thể vào, xáo trộn bộ sưu tập bút chì và chọn ba màu bất kỳ (như đỏ/xanh/tím, như trong ví dụ này) và màu đại diện cho giải pháp. Lưu ý rằng màu cụ thể được sử dụng không quan trọng.

Trước khi rời khỏi nhà kho, Google đội một chiếc mũ lên mỗi đầu. Khi tôi trở lại, đây là tất cả những gì tôi sẽ thấy:


Rõ ràng, phương pháp này sẽ bảo vệ hoàn hảo Bí mật của Google. Nhưng điều này sẽ không giúp tôi chút nào. Có thể Google đang tô màu ngẫu nhiên và do đó không đúng thứ tự. Hoặc có thể họ không điền gì cả.

Để thuyết phục tôi rằng vấn đề đã thực sự được giải quyết, Google cho tôi cơ hội “kiểm tra” kết quả tô màu biểu đồ của họ. Tôi có quyền chọn theo thứ tự ngẫu nhiên một mặt của biểu đồ này (nghĩa là dọc theo một đường thẳng giữa hai chiếc mũ liền kề). Google sẽ bỏ 2 chiếc mũ này ra, cho tôi xem Một phần nhỏ các giải pháp:


Xin lưu ý rằng thử nghiệm của tôi có hai kết quả có thể xảy ra:

Nếu hai đỉnh hiển thị có cùng màu (hoặc hoàn toàn không có màu!) thì tôi biết chắc chắn rằng Google đang nói dối tôi. Trong trường hợp này, tôi sẽ không trả cho Google dù chỉ một xu. Nếu hai đỉnh hiển thị có màu sắc khác nhau, có nghĩa là Google không lừa dối tôi trong trường hợp này.

Tôi hy vọng tuyên bố đầu tiên là rõ ràng. Thứ hai sẽ yêu cầu nhiều hơn giải thích chi tiết. Vấn đề là ngay cả khi thử nghiệm thành công, Google vẫn có thể lừa dối tôi. Tuy nhiên, tôi chỉ nhìn dưới hai chiếc mũ. Nếu có E cạnh riêng biệt trong biểu đồ thì có khả năng Google sẽ đưa ra giải pháp không chính xác. Ví dụ: sau một lần kiểm tra, họ đánh lừa tôi bằng xác suất (E-1)/E (đối với 1000 cạnh sẽ là 99,9%).

May mắn thay, Google có câu trả lời cho câu hỏi này. Chúng ta sẽ chạy lại giao thức!

Chúng tôi lấy giấy trắng để tạo một bản sao mới của biểu đồ. Google hiện đang thực hiện một cuộc ngẫu nhiên mới gồm ba cây bút chì màu. Sau đó, họ điền vào biểu đồ với giải pháp chính xác nhưng sử dụng một bộ ba màu ngẫu nhiên mới.

Một lần nữa chúng tôi thực hiện thao tác với mũ. Tôi quay lại và chọn ngẫu nhiên các đỉnh mới. Chúng ta hãy nhìn lại logic được mô tả ở trên. Lần này, nếu mọi việc suôn sẻ, tôi sẽ tin tưởng hơn nhiều rằng Google đang nói sự thật với tôi. Đó là vì để đánh lừa tôi, Google sẽ phải gặp may hai lần.

Một sự kiện như vậy có thể xảy ra - nhưng xác suất của nó sẽ còn thấp hơn. Khả năng Google đánh lừa tôi hai lần liên tiếp là (E-1)/E*(E-1)/E (hoặc khoảng 99,8% cơ hội cho ví dụ 1000 cạnh của chúng tôi).

May mắn thay, chúng ta không phải dừng lại ở hai lần thử. Chúng tôi sẽ thử đi thử lại cho đến khi chúng tôi tin rằng Google, với khả năng cao, đã nói sự thật.

Tôi mong bạn đừng tin lời tôi. Hãy thử Javascript này và tự mình xem.

Lưu ý rằng tôi không bao giờ hoàn toàn chắc chắn rằng Google đang trung thực - luôn có khả năng rất nhỏ là họ đang lừa dối tôi. Nhưng sau đó số lượng lớn lặp đi lặp lại (E^2, như trong trường hợp của chúng tôi), cuối cùng tôi sẽ đi đến điểm mà Google đang lừa dối tôi với xác suất không đáng kể - đủ để áp dụng thực tế. Sau đó, tôi có thể dễ dàng đưa tiền cho Google.

Điều quan trọng là Google cũng được bảo vệ trong trường hợp này. Nếu tôi cố gắng học bất cứ điều gì bằng cách lưu và phân tích các ghi chú giữa các lần chạy giao thức, tôi sẽ thất bại. Điều này là do Google sử dụng màu sắc ngẫu nhiên trong mỗi lần lặp lại. Thông tin hạn chế, mà tôi có thể nhận được sẽ không mang lại cho tôi bất cứ điều gì. Không có cách nào để tôi liên kết dữ liệu này lại với nhau.

Điều gì khiến ví dụ này trở thành "không có kiến ​​thức"?

Tôi đang cố thuyết phục bạn rằng giao thức này không cho phép thông tin rò rỉ ra ngoài Giải pháp của Google. Nhưng bạn không cần phải tin lời tôi! Nguyên tắc đầu tiên của các nhà mật mã là không bao giờ tin những điều như vậy mà không có bằng chứng.

Goldwasser, Micali và Rakoff đề xuất ba tiêu chí mà mọi giao thức không có kiến ​​thức đều phải đáp ứng. Một cách không chính thức, chúng có thể được mô tả như sau:

Sự hoàn thiện. Nếu Google nói cho tôi biết sự thật thì tôi phải có bằng chứng chắc chắn về điều đó (bằng chứng có xác suất cao). Độ tin cậy. Google chỉ có thể thuyết phục tôi nếu nó thực sự nói lên sự thật. “Không tiết lộ” (tiêu chí này thực sự được gọi như vậy). Tôi không cần phải tìm hiểu gì thêm ngoài giải pháp Google mà tôi có được.

Chúng tôi đã thảo luận về các lập luận cho sự đầy đủ. Giao thức cuối cùng sẽ thuyết phục tôi (với khả năng xảy ra lỗi không đáng kể) nếu tôi chạy nó đủ số lần. Độ tin cậy cũng khá dễ dàng để chứng minh. Nếu Google cố gắng lừa dối tôi, tôi sẽ phát hiện ra điều đó trong phần lớn các trường hợp.

Thuộc tính khó khăn nhất vẫn là “không có kiến ​​​​thức”. Để hiểu nó, chúng ta hãy làm một thí nghiệm tưởng tượng khá kỳ lạ.

Thí nghiệm tưởng tượng với cỗ máy thời gian

Đầu tiên, hãy bắt đầu với một giả định điên rồ. Hãy tưởng tượng rằng các kỹ sư của Google không thông minh như mọi người nghĩ. Họ giải quyết vấn đề này hàng tuần và không thể tìm ra giải pháp. Mười hai giờ trước thời hạn, Google trở nên tuyệt vọng. Họ quyết định lừa tôi và nói rằng họ có một cuốn sách tô màu cho Bá tước (mặc dù thực tế họ không có cuốn nào).

Ý tưởng của họ là ghé qua xưởng GoogleX và mượn nguyên mẫu cỗ máy thời gian của Google. Kế hoạch ban đầu là quay trở lại một vài năm và sử dụng thêm thời gian làm việcđể tìm giải pháp mới cho vấn đề. Thật không may, cũng như nhiều nguyên mẫu khác của Google, cỗ máy thời gian có một số hạn chế. Quan trọng nhất là cô ấy chỉ có thể du hành ngược thời gian bốn phút rưỡi.

Như vậy, không cần thiết phải sử dụng cỗ máy thời gian để tăng thời gian hoàn thành một công việc. Tuy nhiên, hóa ra công nghệ rất hạn chế này có thể được sử dụng để đánh lừa tôi.

Tôi thực sự không biết chuyện gì đang xảy ra ở đây. Nhưng có vẻ như nó sẽ có ích.

Kế hoạch hóa ra đơn giản đến mức quỷ dị. Nếu Google không biết nên tô màu biểu đồ như thế nào, họ sẽ chỉ ngẫu nhiên tô màu giấy rồi đội mũ lên trên. Nếu may mắn thay, các đỉnh có màu sắc khác nhau, tất cả chúng ta sẽ thở phào nhẹ nhõm và tiếp tục làm việc với niềm tin rằng mọi thứ đều ổn.

Giả sử tôi cởi một chiếc mũ ra và phát hiện ra hai đỉnh cùng màu. Nếu giao thức được triển khai theo cách thông thường, Google sẽ thất bại trong trường hợp này. Nhưng chúng ta sử dụng cỗ máy thời gian. Bất cứ khi nào Google thấy mình ở một tình thế khó xử, nó chỉ đơn giản là khắc phục tình hình đó. Tức là được bổ nhiệm đặc biệt nhân viên Google kéo công tắc, thời gian quay ngược lại bốn phút rưỡi, và Nhóm Google tô màu đồ thị bằng một giải pháp ngẫu nhiên hoàn toàn mới. Sau đó, họ tua nhanh thời gian và thử lại.

Về cơ bản, cỗ máy thời gian cho phép Google "sửa" mọi lần đăng nhập thất bại mà tôi không nghi ngờ gì. Vì kết quả xấu sẽ chỉ xảy ra 1/3 thời gian nên thời gian thực thi dự kiến ​​của giao thức (theo quan điểm của Google) chỉ dài hơn một chút so với nếu giao thức được thực thi công bằng. Theo quan điểm của tôi, tôi thậm chí còn không biết việc du hành thời gian này đang diễn ra.

Điểm cuối cùng này là quan trọng nhất. Theo quan điểm của tôi, tôi tương tác với giao thức theo cách tương tự dù có cỗ máy thời gian hay không. Chưa hết, điều đáng chú ý nữa là ở phiên bản cỗ máy thời gian, Google hoàn toàn không có thông tin gì về cách tô màu đồ thị.

Và điều gì xảy ra sau đó?

Những gì chúng tôi vừa trình bày là một ví dụ lý thuyết. Trong một thế giới mà thời gian cứ trôi về phía trước và không ai có thể đánh lừa tôi bằng cỗ máy thời gian, giao thức mũ hoạt động chính xác. Sau E^2 vòng chạy, tôi nên tin tưởng (không hoàn toàn nhưng với xác suất gian lận không đáng kể) rằng biểu đồ được tô màu chính xác và Google đã cung cấp thông tin chính xác.

Nếu thời gian có thể bị thao túng (đặc biệt là nếu Google có thể "tua lại thời gian") thì nó có thể giả mạo giao thức, ngay cả khi nó không có thông tin nào về cách tô màu biểu đồ.

Theo quan điểm của tôi, sự khác biệt giữa hai giao thức này là gì? Chúng có cùng phân bố thống kê và truyền tải cùng một lượng thông tin hữu ích.

Dù bạn có tin hay không, điều này chứng tỏ một điều rất quan trọng.

Cụ thể, người ta cho rằng tôi (Người xác minh) ​​có một số loại chiến lược cho phép tôi "trích xuất" thông tin hữu ích về cách Google thực hiện tô màu nếu giao thức trung thực được chạy. Sau đó, chiến lược của tôi cũng sẽ có hiệu quả nếu tôi bị cỗ máy thời gian đánh lừa. Theo quan điểm của tôi, các giao thức chạy giống hệt nhau về mặt thống kê. Về mặt thể chất tôi không thể chỉ ra sự khác biệt.

Như vậy, lượng thông tin mà tôi sẽ nhận được trong “thí nghiệm thực tế” và “thử nghiệm cỗ máy thời gian” là hoàn toàn giống nhau. Lượng thông tin mà Google đưa vào thử nghiệm cỗ máy thời gian chính xác là bằng không. Vì vậy, ngay cả trong thế giới thực cũng sẽ không có hiện tượng rò rỉ thông tin. Tất cả những gì còn lại là chứng minh rằng các nhà khoa học máy tính có cỗ máy thời gian (suỵt, đó là bí mật).

Làm thế nào để thoát khỏi chiếc mũ và cỗ máy thời gian

Tất nhiên, chúng tôi thực sự không muốn chạy giao thức bằng cách sử dụng mũ. Và ngay cả Google (rất có thể) cũng không có cỗ máy thời gian thực.

Để gắn kết tất cả những thứ này lại với nhau, chúng ta cần đưa giao thức này vào thế giới kỹ thuật số. Để làm được điều này, chúng ta cần một thứ kỹ thuật số tương đương với “chiếc mũ”: thứ gì đó che giấu ý nghĩa kỹ thuật số, đồng thời “ràng buộc” ý nghĩa và người tạo ra nó (tạo ra một “cam kết”), để anh ta không thể thay đổi ý định .

May mắn thay, chúng tôi có một công cụ tuyệt vời cho ứng dụng này. Nó được gọi là chương trình cam kết kỹ thuật số. Sơ đồ cam kết cho phép một bên tạo "cam kết" cho một tin nhắn, giữ bí mật và sau đó mở "cam kết" để xem nội dung bên trong. Chúng có thể được xây dựng từ Các thành phần khác nhau, kể cả từ kẻ mạnh chức năng mật mã băm.

Sau khi nhận được sơ đồ cam kết, chúng tôi đã lắp ráp tất cả các thành phần để khởi động ở dạng điện tử giao thức không có kiến ​​thức. Đầu tiên người thử nghiệm mã hóa màu của các đỉnh thành một tập hợp tin nhắn kỹ thuật số(ví dụ: các số 0, 1, 2), sau đó tạo nghĩa vụ kỹ thuật số cho mỗi số. Các nghĩa vụ này được chuyển đến Kiểm soát viên. Khi Bộ điều khiển mở một cạnh, Bộ kiểm tra sẽ hiển thị các giá trị cho các nghĩa vụ tương ứng với hai đỉnh.

Đây là cách chúng tôi đã loại bỏ được những chiếc mũ. Nhưng làm thế nào để chúng tôi chứng minh rằng giao thức này không có kiến ​​thức?

Nhưng bây giờ chúng ta đang ở trong thế giới kỹ thuật số. Do đó, chúng tôi không cần cỗ máy thời gian để xác nhận rằng giao thức hoạt động. Bí quyết chính là giao thức sẽ không hoạt động giữa hai người mà giữa hai chương trình máy tính khác nhau (hoặc chính thức hơn là hai máy Turing xác suất.)

Bây giờ chúng ta có thể chứng minh định lý sau: nếu Bộ điều khiển trích xuất thông tin hữu ích từ một lần chạy giao thức bình thường, anh ta sẽ nhận được cùng một lượng thông tin hữu ích như từ một lần chạy "gian lận" của giao thức mà Người kiểm tra không đưa vào bất kỳ thông tin nào để bắt đầu.

Chúng ta đang nói về các chương trình máy tính và chúng có thể “quay ngược thời gian”. Ví dụ: hãy cân nhắc sử dụng máy ảo có thể chụp ảnh nhanh. Ví dụ về "tua lại thời gian" bằng cách sử dụng máy ảo. Ban đầu, máy ảo đi theo một đường dẫn, quay về trạng thái ban đầu, sau đó thực thi các nhánh tới một đường dẫn mới.


Ngay cả khi chúng ta không xem xét các máy ảo thì bất kỳ chương trình máy tính nào cũng có thể được "tua lại" thành trạng thái trước đó, chỉ đơn giản bằng cách chạy chương trình ngay từ đầu và gửi dữ liệu giống như dữ liệu đầu vào. Với điều kiện là các đầu vào (bao gồm cả đầu vào Số ngẫu nhiên), được cố định thì chương trình sẽ luôn đi theo cùng một đường dẫn thực thi. Vì vậy, chúng ta có thể tua lại chương trình, bắt đầu lại từ đầu và “phân nhánh” quá trình thực thi của nó khi chương trình đạt đến một điểm mong muốn nhất định.

Cuối cùng, những gì chúng ta nhận được có thể được biểu diễn dưới dạng một định lý. Nếu đối với Bộ điều khiển có chương trình máy tính, trích xuất thành công thông tin hữu ích từ Người kiểm tra (bằng cách tương tác với giao thức), sau đó Người kiểm tra có thể sử dụng thủ thuật tua lại chương trình, cung cấp các giải pháp ngẫu nhiên cho Bộ điều khiển. Nó sử dụng logic tương tự như chúng ta đã áp dụng ở trên: nếu Bộ điều khiển có thể trích xuất thành công thông tin bằng cách chạy một giao thức thực, thì nó sẽ thu được cùng một lượng thông tin bằng cách chạy một giao thức giả dựa trên việc tua lại chương trình. Nhưng vì giao thức giả mạo không truyền bất kỳ dữ liệu hữu ích nào nên không có thông tin nào có thể được trích xuất. Như vậy, thông tin mà Controller có thể trích xuất luôn bằng 0.

Điều gì xảy ra sau tất cả những điều này?

Tóm lại, chúng ta có thể nói rằng giao thức này đã hoàn chỉnh và đáng tin cậy. Chúng ta có thể nói về độ tin cậy trong mọi tình huống mà cả hai bên đều không cố gắng lừa dối lẫn nhau.

Đồng thời, giao thức không có kiến ​​thức. Để chứng minh điều này, chúng tôi đã chỉ ra rằng một chương trình mà Bộ điều khiển chạy để trích xuất thông tin sẽ có thể trích xuất dữ liệu từ một chương trình không có dữ liệu có ý nghĩa. Điều này dẫn đến một mâu thuẫn rõ ràng, cho chúng ta biết rằng giao thức trong mọi tình huống không bị rò rỉ thông tin.

Điều này mang lại cho chúng tôi những lợi thế quan trọng. Vì bất kỳ ai cũng có thể tạo bản ghi giả (như ví dụ trên Google khi họ cố gắng thuyết phục tôi rằng họ có giải pháp), tôi không thể phát lại bản ghi để chứng minh trường hợp của mình với bất kỳ ai khác (chẳng hạn như thẩm phán). Thẩm phán sẽ nói rằng ông ta không chắc chắn rằng đoạn ghi âm được thực hiện một cách trung thực và không bị chỉnh sửa (như trong ví dụ với Google và việc sử dụng cỗ máy thời gian). Điều này có nghĩa là bản ghi chép không chứa bất kỳ thông tin nào. Giao thức chỉ có ý nghĩa nếu bản thân tôi tham gia và có thể chắc chắn rằng mọi thứ diễn ra trong thời gian thực.

Bằng chứng cho tất cả các NP!

Đối với những người đã làm được điều này, tôi có một tin quan trọng. Bản thân nhiệm vụ tô màu mạng di động bằng ba màu rất thú vị, nhưng đó không phải là tất cả. Cho thật điều thú vị về bài toán tô màu ba màu là nó thuộc lớp NP-đầy đủ. Điều này có nghĩa là bất kỳ vấn đề nào khác thuộc lớp NP đều có thể được quy về vấn đề này.

Nói một cách đơn giản, Goldrich, Micali và Widgerson đã chứng minh rằng ZK "hiệu quả" tồn tại cho một loạt các bài toán hữu ích. Nhiều trong số chúng thú vị hơn nhiều so với vấn đề ấn định tần số trong mạng di động.

Bạn chỉ cần tìm câu lệnh (trong NP) mà bạn muốn kiểm tra và chuyển nó thành bài toán tô màu đồ thị ba màu. Từ thời điểm này, bạn có thể chạy phiên bản kỹ thuật số của giao thức của chúng tôi với mũ.

Thay vì kết quả

Tất nhiên, sẽ cực kỳ ngu ngốc nếu bắt đầu sử dụng giao thức này ngay lập tức trong thực tế. Chi phí tính toán của nó sẽ bao gồm kích thước tổng thể tuyên bố và bằng chứng ban đầu, cộng với chi phí chuyển vấn đề thành biểu đồ và một lần chạy E^2 khác của giao thức, cần thiết để xác minh tính đúng đắn của giải pháp. Về lý thuyết, điều này là "hiệu quả", nhưng vì tổng chi phí của việc chứng minh sẽ là đa thức của độ dài đầu vào nên nó không thể áp dụng được trong thực tế.

Vì vậy cho đến nay chúng ta chỉ chứng minh được rằng những bằng chứng như vậy là có thể thực hiện được. Vẫn còn phải tìm bằng chứng đủ thực tế để sử dụng thực sự.

Ghi chú

* Về mặt chính thức, mục đích của bằng chứng tương tác là thuyết phục Bên kiểm soát rằng chuỗi cụ thể thuộc về bất kỳ ngôn ngữ nào. Thông thường, Người kiểm tra trong các nhiệm vụ có quyền lực vô hạn và Người điều khiển bị hạn chế về khả năng thực hiện các phép tính.

**Ví dụ này dựa trên giải pháp ban đầu Goldwasser, Micali và Rakoff, và ví dụ hướng dẫn sử dụng mũ do Silvio Micali thiết kế.

****** Một ví dụ đơn giản về cam kết có thể được xây dựng bằng cách sử dụng hàm băm mẫu. Để tạo cam kết về giá trị "x", chúng tôi chỉ cần tạo một số chuỗi số ngẫu nhiên (đủ dài) mà chúng tôi gọi là "muối" và cam kết đầu ra là C = hash(salt || x). Để mở một cam kết, bạn chỉ cần mở "x" và "muối". Bất cứ ai cũng có thể xác minh rằng cam kết ban đầu là hợp lệ bằng cách tính toán lại hàm băm. Cái này phương pháp an toàn theo một số giả định khá mạnh về bản thân hàm số đó.

Chúng tôi đã xem xét Zk-SNARK hoặc giao thức chứng minh không có kiến ​​thức là gì. nói một cách đơn giản, nhưng trong bài viết này chúng tôi muốn đi sâu hơn vào phần kỹ thuật của hiện tượng này.

Giao thức chứng minh không có kiến ​​thức: Nó hoạt động như thế nào?

Vì vậy, xin nhắc lại, bằng chứng thỏa thuận vô hiệu cho phép bạn chứng minh rằng bạn là chủ sở hữu của một số thông tin mà không tiết lộ nội dung của nó. Để thực hiện khái niệm này, cần phải giới thiệu 3 thuật toán cùng một lúc, chúng tôi sẽ ký hiệu là GK, P và V. Hãy xem xét mục đích của chúng:

  • GK là một trình tạo khóa chấp nhận đầu vào α và chương trình C, tạo ra hai khóa: khóa xác minh cho PK người kiểm chứng và khóa xác minh cho VK xác minh. Các khóa này được công khai cho tất cả các bên liên quan đến bằng chứng.
  • P là người dùng cần sử dụng 3 loại dữ liệu đầu vào để chứng minh: 1) khóa xác minh PK; 2) đầu vào ngẫu nhiên X, sẽ được cung cấp công khai cho các bên; 3) một tuyên bố cần được chứng minh mà không tiết lộ ý nghĩa của nó - W. Bản thân thuật toán P tạo ra Bằng chứng chứng minh, sẽ thỏa mãn các điều kiện sau: Bằng chứng = P (PK; X; W).
  • V là thuật toán xác minh trả về biến Boolean. Nó có thể được biểu thị bằng hai giá trị: TRUE (true) hoặc FALS (false). Vì vậy, trình xác minh lấy dữ liệu đầu vào sau V(VK; X; Proof), dựa vào đó nó xác định xem nó đúng hay sai.

Đây là cách hoạt động của giao thức chứng minh không có kiến ​​thức. Điều duy nhất tôi muốn nói riêng là ý nghĩa α, được đề cập trong đoạn văn về GK. Sự thật là thông số này làm phức tạp đáng kể việc sử dụng Zk-SNARK trong các ứng dụng thực tế, bởi vì bất kỳ ai sở hữu nó đều có thể tạo Bằng chứng sai mà hệ thống sẽ trả về Đúng. Các nhà phát triển ZCash, một loại tiền điện tử sử dụng công nghệ zero-proof, đã phải vật lộn với vấn đề này trong một thời gian rất dài.

Một trong mặt tốt nhất mật mã hiện đại là thuật ngữ hay của nó. Bạn có thể tạo bao nhiêu ban nhạc punk tùy thích với những cái tên như Hardcore Predicate, Trapdoor Function hoặc Impossible Differential Cryptanalysis. Tuy nhiên, có một thuật ngữ vượt qua tất cả những thuật ngữ khác. Đây là Bằng chứng Không có Kiến thức - "không có bằng chứng kiến ​​thức".

Thuật ngữ “không có kiến ​​thức” hấp dẫn đến mức dẫn đến nhiều vấn đề. Mọi người sử dụng nó không chính xác, cho rằng không có kiến ​​thức là một từ đồng nghĩa "bảo mật rất, rất đáng tin cậy". Do đó, nó được sử dụng với mọi thứ - bao gồm cả hệ thống mã hóa và mạng ẩn danh - thực sự không liên quan gì đến các giao thức không có kiến ​​thức.

Tôi viết điều này để nhấn mạnh rằng bằng chứng không có kiến ​​thức là một trong những công cụ mạnh mẽ nhất từng được các nhà mật mã phát minh ra. Thật không may, chúng được hiểu một cách kém cỏi. Trong loạt bài đăng này, tôi sẽ cố gắng mô tả rõ ràng bằng chứng không có kiến ​​thức là gì và điều gì khiến chúng trở nên đặc biệt. Chúng ta cũng sẽ xem xét một số giao thức không có kiến ​​thức được sử dụng trong thế giới thực.

Lịch sử của kiến ​​​​thức không

Khái niệm “không có kiến ​​thức” lần đầu tiên được đề xuất vào những năm 1980 bởi các nhà nghiên cứu MIT Shafi Goldwasser, Silvio Micali và Charles Rackoff. Họ đã nghiên cứu các vấn đề liên quan đến hệ thống chứng minh tương tác - hệ thống lý thuyết trong đó một bên ("Người chứng minh") trao đổi thông điệp với bên thứ hai ("Người xác minh") cố gắng thuyết phục họ về sự thật của một số tuyên bố toán học.*

Trước Goldwasser và các đồng nghiệp của cô, công việc trong lĩnh vực này chủ yếu tập trung vào tính đúng đắn của hệ thống chứng minh. Nói cách khác, các nhà khoa học đã xem xét các tình huống trong đó Người kiểm chứng độc ác cố gắng “đánh lừa” Người xác minh tin vào một tuyên bố sai. Goldwasser, Micali và Rekoff đã lật ngược vấn đề. Thay vì chỉ lo lắng về Prover, họ quyết định xem xét điều gì sẽ xảy ra nếu bạn không tin tưởng Gửi thanh tra.

Vấn đề cụ thể mà họ đặt ra là rò rỉ thông tin. Các nhà khoa học đã tự hỏi Người xác minh học được bao nhiêu thông tin bổ sung trong quá trình chứng minh ngoài thực tế là tuyên bố đó là đúng.

Điều quan trọng cần lưu ý là điều này không chỉ được thực hiện vì lợi ích lý thuyết - những vấn đề như vậy có ứng dụng trong thế giới thực. Đây là một tình huống như vậy: Hãy tưởng tượng một người dùng trong thế giới thực muốn đăng nhập vào máy chủ web bằng mật khẩu. Cách tiếp cận "thực tế" tiêu chuẩn cho vấn đề này liên quan đến việc lưu trữ phiên bản băm của mật khẩu trên máy chủ. Vì vậy, việc đăng nhập vào máy chủ có thể được coi là một loại “bằng chứng” cho thấy hàm băm mật khẩu là kết quả của việc áp dụng hàm băm cho một số mật khẩu và trên thực tế, máy khách là biết mật khẩu.

Số đông hệ thống thực triển khai “bằng chứng” này theo cách tồi tệ nhất có thể: máy khách chỉ cần chuyển mật khẩu gốc đến máy chủ, máy chủ sẽ tính toán hàm băm của mật khẩu và so sánh nó với giá trị được lưu trữ. Nhược điểm của phương pháp này là rõ ràng: máy chủ đã biết được mật khẩu không được mã hóa của khách hàng. Do đó, việc vệ sinh mật khẩu hiện đại phần lớn dựa trên giả định rằng máy chủ không bị xâm phạm.

Những gì Goldwasser, Micali và Rekoff đề xuất đã mang lại hy vọng mới cho việc triển khai các bằng chứng không có kiến ​​thức mà có thể chứng minh được là không thể nói được không có thông tin ngoại trừ một bit có nghĩa là “tuyên bố này là đúng”.

Ví dụ về "Thế giới thực"

Cuộc thảo luận của chúng ta hiện tại khá trừu tượng, vì vậy hãy xem một ví dụ "thế giới thực" về giao thức không có kiến ​​thức (hơi điên rồ).

Hãy tưởng tượng tôi là một ông trùm viễn thông đang triển khai một mạng di động mới. Cấu trúc mạng của tôi được hiển thị trong hình bên dưới. Mỗi đỉnh trong biểu đồ này đại diện cho một tháp vô tuyến và các cạnh của biểu đồ cho biết vị trí mà các ô chồng chéo, nghĩa là nơi việc thu tín hiệu có thể gặp khó khăn. May mắn thay, để tránh nhiễu, tôi có thể chỉ định mỗi tháp cho một trong ba dải tần số khác nhau.

Vì vậy vấn đề triển khai mạng là làm thế nào để phân công dải tần số tháp sao cho không có hai ô chồng chéo nào sử dụng cùng tần số. Bằng cách biểu thị các dải tần số bằng các màu khác nhau, chúng ta có thể nhanh chóng đề xuất một giải pháp cho vấn đề:

Tất nhiên, nhiều bạn đã nhận ra rằng đây chỉ là một ví dụ của bài toán lý thuyết nổi tiếng về việc tô màu đồ thị bằng ba màu. Vấn đề này rất thú vị vì đối với một số đồ thị rất khó tìm ra lời giải hoặc thậm chí không biết nó tồn tại Nó. Trên thực tế, tô màu ba màu—chính xác hơn là tìm hiểu xem liệu có thể tô màu một đồ thị cụ thể bằng ba màu hay không—nằm trong lớp phức tạp NP.

Rõ ràng ví dụ về đồ chơi của chúng ta rất dễ giải quyết bằng tay, nhưng nếu không thì sao? Ví dụ, hãy tưởng tượng rằng mạng di động của tôi rất lớn và phức tạp - đến mức tài nguyên máy tính mà tôi sử dụng không đủ để tìm ra giải pháp. Trong trường hợp này nó sẽ là mong muốn thuê ngoài vấn đề cho người khác có nhiều tài nguyên máy tính hơn. Ví dụ: tôi có thể nhờ bạn bè ở Google giải quyết giúp tôi theo thông số kỹ thuật.

Nhưng điều này dẫn đến một vấn đề.

Giả sử rằng Google dành một phần đáng kể cơ sở hạ tầng máy tính của mình để tìm cách tô màu biểu đồ của tôi. Tất nhiên, tôi sẽ không trả tiền cho họ cho đến khi tôi biết rằng họ thực sự đã tìm ra cách như vậy, nhưng đồng thời giờ Google sẽ không đưa cho tôi bản sao quyết định cho đến khi tôi trả tiền cho họ. Chúng ta đang ở ngõ cụt.

Có lẽ có một cách thực tế để thoát khỏi tình trạng bế tắc này, bao gồm cả việc nhờ đến luật sư và sử dụng tài khoản ký quỹ, nhưng đây không phải là một blog về cuộc sống thực mà là về mật mã. Nếu bạn đã từng đọc bất kỳ nghiên cứu nào về tiền điện tử, bạn sẽ nhận ra rằng Đúng cáchđể giải quyết vấn đề này là đưa ra một giải pháp kỹ thuật hoàn toàn điên rồ.

Giải pháp kỹ thuật điên rồ (có mũ!)

Lưu ý rằng tôi sẽ không bao giờ chắc chắn tuyệt đối rằng Google trung thực - sẽ luôn có ít nhất một khả năng nhỏ là Google đang lừa dối tôi. Tuy nhiên, sau một số lần lặp lớn (cụ thể là E^2 ) sự tự tin của tôi sẽ tăng lên đến mức xác suất Google bị lừa là không đáng kể - khá nhỏ, vậy nên trong mọi người vấn đề thực tế cô ấy có thể bị bỏ rơi. Bằng cách này, tôi có thể đưa tiền của mình cho Google một cách an toàn.

Chúng ta cần biết rằng Google cũng an toàn. Ngay cả khi tôi đang cố gắng tìm hiểu điều gì đó về giải pháp của Google bằng cách ghi chú giữa các lần chạy giao thức, điều đó cũng không thành vấn đề. Tôi bị bối rối bởi Google chọn ngẫu nhiên lựa chọn màu sắc trong các lần lặp khác nhau của giao thức. Thông tin hạn chế tôi nhận được là vô ích và tôi không có cách nào buộc dữ liệu từ các lần lặp khác nhau.

Điều gì làm nên "không có kiến ​​thức" này?

Trước đây tôi đã tuyên bố rằng giao thức này ngăn cản quyết định của Google bị rò rỉ, nhưng đừng để tôi thoát khỏi dễ dàng như vậy! Nguyên tắc đầu tiên của mật mã hiện đại là đừng bao giờ tin người người đưa ra những tuyên bố như vậy mà không có bằng chứng.

Goldwasser, Micali và Rekoff đề xuất ba thuộc tính mà bất kỳ giao thức không có kiến ​​thức nào cũng phải đáp ứng. Một cách không chính thức, chúng có thể được thể hiện như sau:

  1. Tính đầy đủ (sự đầy đủ). Nếu Google nói sự thật thì cuối cùng nó sẽ có thể thuyết phục được tôi (ít nhất là với xác suất cao).
  2. Tính đúng đắn (sự lành mạnh). Google có thể thuyết phục tôi về quyết định đúng đắn chỉ một trong trường hợp đó, Nếu như thực sự nói sự thật.
  3. Không có kiến ​​thức (số không— sự hiểu biết) . Tôi không nghe thấy gì thêm về quyết định của Google.

Chúng ta đã thảo luận về lập luận về tính đầy đủ. Giao thức này sao cho sau đủ số lần lặp lại, cuối cùng Google sẽ thuyết phục được tôi (với khả năng xảy ra lỗi không đáng kể). Việc chứng minh tính đúng đắn của giao thức này cũng khá dễ dàng. Nếu Google cố gắng lừa dối tôi, tôi gần như chắc chắn sẽ phát hiện ra sự phản bội.

Tính chất thứ ba có vấn đề ở đây, nhưng để hiểu điều này, chúng ta cần thực hiện một thí nghiệm tưởng tượng rất kỳ lạ.

Thí nghiệm tư duy (với cỗ máy thời gian)

Hãy bắt đầu với một giả thuyết điên rồ. Hãy tưởng tượng rằng các kỹ sư của Google không có tay nghề cao như họ tưởng. Họ đã giải quyết vấn đề của tôi hàng tuần, hàng tháng, nhưng họ không thể tìm ra giải pháp. Khi còn 12 giờ trước khi xác minh, nhân viên Google trở nên tuyệt vọng. Họ quyết định lừa dối tôi nên tôi nghĩ họ có cách tô màu đồ thị trong khi thực tế thì không.

Ý tưởng của họ là thâm nhập vào xưởng GoogleX và mượn nguyên mẫu cỗ máy thời gian của Google. Ban đầu họ dự định du hành ngược thời gian vài năm để sử dụng thời gian làm việc thêm để giải quyết vấn đề. Thật không may, giống như hầu hết các nguyên mẫu của Google, cỗ máy thời gian có một số hạn chế: nó chỉ cho phép bạn du hành ngược thời gian bằng cách bốn phút rưỡi.

Do đó, tùy chọn sử dụng cỗ máy thời gian để có thêm thời gian làm việc đã bị loại bỏ. Tuy nhiên, hóa ra ngay cả công nghệ rất hạn chế này vẫn có thể được sử dụng để đánh lừa tôi.

Tôi không biết chuyện gì đang xảy ra ở đây, nhưng tôi nghĩ bức ảnh này rất phù hợp.

Kế hoạch thật đơn giản. Bởi vì Google thực sự không biết tô màu đồ thị hợp lệ, Google chỉ cần tô màu tờ giấy với các màu ngẫu nhiên rồi chọn mũ. Nếu tình cờ chúng ta bắt gặp một cặp đỉnh có màu khác nhau, mọi người sẽ thở phào nhẹ nhõm và chúng ta sẽ tiếp tục làm theo giao thức. Càng xa càng tốt.

Tuy nhiên, chắc chắn sớm muộn gì tôi cũng sẽ đội mũ, khám phá hai đỉnh một màu sắc và bắt Google gian lận. Và đây là lúc cỗ máy thời gian xuất hiện. Khi Google thấy mình trong tình huống kỳ lạ này, nó chỉ đơn giản là loại bỏ nó. Nói cách khác, một “nhân viên Google” đặc biệt sẽ bật công tắc bật tắt, “tua lại” thời gian khoảng bốn phút và nhóm Google sẽ tô màu lại hoàn toàn biểu đồ bằng một giải pháp ngẫu nhiên mới. Sau đó họ bắt đầu lại thời gian, cho phép tôi thử lại.

Về cơ bản, cỗ máy thời gian cho phép Google "khôi phục" sau mọi điều tồi tệ xảy ra trong quá trình thực thi giao thức giả mạo của họ, điều này khiến mọi thứ đối với tôi dường như bình thường. Bởi vì cố gắng tốt thách thức giao thức chỉ xảy ra trong khoảng 1/3 số lần thử, thời gian thực hiện dự kiến ​​của giao thức (theo quan điểm của Google) chỉ dài hơn vừa phải so với thời gian thực hiện của giao thức công bằng. Về phần tôi, tôi thậm chí còn không nghi ngờ rằng việc du hành thời gian đang diễn ra.

Điểm cuối cùng là quan trọng nhất. Trên thực tế, theo quan điểm của tôi, việc không biết có liên quan đến cỗ máy thời gian sẽ dẫn đến chính xác sự tương tác giống như thực tế. Về mặt thống kê chúng giống hệt nhau. Chưa hết, một lần nữa điều đáng chú ý là trong phiên bản có cỗ máy thời gian TạiGoogle Hoàn toàn không có thông tin về cách tô màu đồ thị.

Tất cả những thứ này để làm gì?

Những gì chúng ta vừa xem là một ví dụ mô phỏng. Lưu ý rằng trong một thế giới mà thời gian chỉ chuyển động về phía trước và không ai có thể đánh lừa tôi bằng cỗ máy thời gian, giao thức đội mũ Chính xác, tức là sau E^2 vòng, tôi phải bị thuyết phục (vượt quá xác suất không đáng kể) rằng trên thực tế, biểu đồ có thể được tô màu và Google có giải pháp hợp lệ.

Chúng tôi vừa chỉ ra rằng nếu thời gian không trôi về phía trước - chính xác hơn là nếu Google có thể "tua lại" ý tưởng của tôi về thời gian - thì Google có thể giả mạo hoạt động thực tế của giao thức ngay cả khi không có thông tin về màu sắc thực tếeđồ thị.

Theo quan điểm của tôi, sự khác biệt giữa hai tùy chọn giao thức là gì? Nếu chúng ta xem xét sự phân bổ thống kê của chúng thì không có sự khác biệt - cả hai đều báo cáo lượng thông tin hữu ích gần như nhau.

Dù bạn có tin hay không, điều này chứng tỏ một điều rất quan trọng.

Giả sử tôi (Người xác minh) ​​có một số chiến lược "trích xuất" thông tin hữu ích về màu sắc của Google sau khi quan sát việc thực hiện một giao thức trung thực. Sau đó, chiến lược của tôi sẽ hoạt động hiệu quả như nhau trong trường hợp tôi bị cỗ máy thời gian đánh lừa. Theo quan điểm của tôi, các lần chạy giao thức giống hệt nhau về mặt thống kê - về mặt vật lý, tôi không thể nhận ra sự khác biệt.

Vì vậy, nếu lượng thông tin tôi có thể trích xuất trong "thử nghiệm thực tế" và "thử nghiệm cỗ máy thời gian" giống hệt nhau, nhưng lượng thông tin mà Google cung cấp trong "thử nghiệm cỗ máy thời gian" chính xác bằng 0, điều này cho thấy rằng ngay cả trong trong thế giới thực, giao thức sẽ không tạo ra bất kỳ thông tin hữu ích nào. Tất cả những gì còn lại là chứng minh rằng các nhà khoa học máy tính có cỗ máy thời gian. Vâng, chúng tôi có chúng! (Đây là một bí mật được bảo vệ chặt chẽ.)

Loại bỏ mũ (và cỗ máy thời gian)

Tất nhiên, chúng tôi thực sự không muốn thực hiện giao thức mũ và thậm chí Google cũng không có cỗ máy thời gian thực (có thể).

Để gắn kết mọi thứ lại với nhau, trước tiên chúng ta cần đưa giao thức của mình vào thế giới kỹ thuật số. Điều này đòi hỏi chúng tôi phải xây dựng tương đương kỹ thuật số của một "chiếc mũ" - thứ vừa che giấu ý nghĩa kỹ thuật số vừa "ràng buộc" người sáng tạo với nó ("bắt buộc") để anh ta không thể thay đổi ý định sau khi thực tế.

May mắn thay, chúng tôi có công cụ hoàn hảo cho việc này, được gọi là Chương trình cam kết kỹ thuật số. Một cơ chế cam kết cho phép một bên "cam kết" thực hiện tin nhắn cụ thể, cất vào “phong bì bí mật” rồi sau đó “mở” phong bì cam kết để lộ nội dung bên trong. Các cam kết có thể được tạo từ nhiều thành phần khác nhau, bao gồm các hàm băm mật mã (mạnh).***

Với kế hoạch cam kết, chúng tôi có mọi thứ cần thiết để thực thi điện tử giao thức không có kiến ​​thức. Trước tiên, bộ chuẩn mã hóa màu của các đỉnh dưới dạng một tập hợp các thông báo kỹ thuật số (ví dụ: sử dụng các số 0, 1, 2), sau đó tạo ra các nghĩa vụ kỹ thuật số cho từng thông báo đó. Những nghĩa vụ này được chuyển đến Người đánh giá. Khi Người xác minh thách thức quyết định về một cạnh, Người chứng minh chỉ cần công bố các giá trị cho các cam kết tương ứng với hai đỉnh.

Vì vậy, chúng tôi đã loại bỏ những chiếc mũ, nhưng làm cách nào chúng tôi có thể chứng minh rằng đó là một giao thức không có kiến ​​thức?

May mắn thay, chúng ta hiện đang ở trong thế giới kỹ thuật số và chúng ta không cần xe thậtđã đến lúc chứng minh những tuyên bố về giao thức này. Bí quyết chính là chỉ ra rằng giao thức sẽ không hoạt động giữa mọi người, và giữa hai điểm khác nhau chương trình máy tính(hay nói một cách chính thức hơn là máy Turing xác suất).

Bây giờ chúng ta có thể chứng minh định lý sau. Nếu một chương trình máy tính có thể được tạo (cho Người xác minh) ​​để trích xuất thông tin hữu ích sau khi tham gia chạy giao thức, thì có thể sử dụng "cỗ máy thời gian" với chương trình đó để chương trình trích xuất cùng một lượng thông tin hữu ích từ một Giao thức "giả" chạy khi Prover không cung cấp thông tin.

Và vì bây giờ chúng ta đang nói về chương trình máy tính, rõ ràng, việc tua lại thời gian không phải là một khả năng phi thường chút nào. Trên thực tế, chúng ta tua lại các chương trình máy tính mọi lúc. Ví dụ: hãy lấy phần mềm dành cho máy ảo có chức năng chụp nhanh.

Một ví dụ về tua lại ảnh chụp nhanh của máy ảo. VM ban đầu được phát tiếp, hoàn nguyên về ảnh chụp nhanh ban đầu và sau đó một nhánh khác được thực thi.

Ngay cả khi bạn không có phần mềm máy ảo ưa thích, bất kỳ chương trình máy tính nào cũng có thể được "tua lại" thành nhiều hơn. trạng thái sớm, chỉ cần bắt đầu lại từ đầu và chuyển chính xác cùng một đầu vào. Nếu đầu vào - bao gồm tất cả các số ngẫu nhiên - là cố định, chương trình sẽ luôn đi theo cùng một đường dẫn thực hiện. Bạn có thể tua lại một chương trình bằng cách chỉ cần khởi động nó lại từ đầu và "ngắt" quá trình thực thi của nó khi nó đạt đến một số điểm mong muốn.

Cuối cùng ta thu được định lý sau. Nếu có một số chương trình máy tính của Người xác minh trích xuất thành công thông tin bằng cách thực thi tương tác giao thức này với một số Prover, thì chúng ta có thể chỉ cần sử dụng thủ thuật tua lại để thể hiện cam kết đối với một giải pháp ngẫu nhiên, sau đó "đánh lừa" Người xác minh bằng cách tua lại chương trình cho đến khi vượt qua sự thử nghiệm. Logic tương tự được áp dụng như trên: nếu Người xác minh đó thành công trong việc trích xuất thông tin sau khi thực hiện giao thức thực tế thì nó có thể trích xuất cùng một lượng thông tin từ một giao thức tua lại mô phỏng. Nhưng vì không có thông tin nào được chuyển đến giao thức mô phỏng nên không có gì để trích xuất. Do đó, lượng thông tin mà Người xác minh có thể trích xuất là bằng không.

Được rồi, vậy tất cả điều này có nghĩa là gì?

Vì vậy, từ phân tích trên, chúng ta biết rằng giao thức đã hoàn chỉnh và chính xác. Lập luận về tính đúng đắn có hiệu lực bất cứ khi nào chúng ta biết rằng không có ai đang thao túng thời gian - nghĩa là chương trình của Người xác minh đang chạy bình thường và không có ai tua lại quá trình thực thi của nó.

Đồng thời, giao thức cũng cung cấp kiến ​​thức bằng không. Để chứng minh điều này, chúng tôi đã chỉ ra rằng bất kỳ chương trình Người xác minh nào trích xuất thông tin thành công cũng phải có khả năng trích xuất thông tin từ giao thức tua lại chạy khi không có thông tin ban đầu có sẵn.Điều này dẫn đến một mâu thuẫn rõ ràng và cho chúng ta biết rằng việc rò rỉ thông tin khi thực hiện một giao thức như vậy là không thể xảy ra trong cả hai trường hợp.

Tất cả điều này có lợi thế quan trọng. Vì bất kỳ ai cũng có thể dễ dàng “làm giả” một mục nhập giao thức ngay cả sau khi hệ thống Google chứng minh cho tôi thấy cô ấy có giải pháp, tôi không thể xem lại bản ghi để chứng minh bất cứ điều gì với bất kỳ ai khác (chẳng hạn như thẩm phán). Đó là vì thẩm phán không đảm bảo rằng video được ghi lại một cách công bằng và tôi đã không đã chỉnh sửa nó giống như cách mà hệ thống Google có thể thực hiện với sự trợ giúp của cỗ máy thời gian. Điều này có nghĩa là bản thân mục nhật ký không chứa thông tin. Giao thức chỉ có ý nghĩa nếu bản thân tôi tham gia vào nó và chắc chắn rằng nó diễn ra trong thời gian thực.

Bằng chứng cho tất cả các NP!

Nếu bạn đã đọc đến đây, tôi chắc chắn rằng bạn đã sẵn sàng đón nhận một số tin tức quan trọng. Cụ thể là bạn sắp biết rằng mạng di động ba màu không phải là một vấn đề thú vị—ít nhất là không phải riêng lẻ.

Bài toán 3 màu thú vị chủ yếu vì nó thuộc lớp NP-đầy đủ. Nói một cách không chính thức, điều đáng ngạc nhiên về những vấn đề này là bất kỳ vấn đề nào khác từ lớp học N.P. có thể được chuyển đổi thành một trường hợp của vấn đề này.

Kết quả này, trong một cú trượt ngã - nhờ Goldreich, Micali và Widjerson - chứng minh rằng các bằng chứng không có kiến ​​thức "hiệu quả" tồn tại cho một loạt các phát biểu hữu ích, nhiều trong số đó nhiều hơn nữa thú vị hơn việc phân bổ tần số mạng di động. Bạn chỉ cần tìm câu lệnh (trong lớp NP) mà bạn muốn chứng minh, chẳng hạn như ví dụ về hàm băm của chúng tôi ở trên, sau đó chuyển nó thành một thể hiện của bài toán 3 màu. Sau đó, bạn chỉ cần chạy phiên bản kỹ thuật số của giao thức có mũ.

Hãy tóm tắt lại

Tất nhiên, việc thực sự chạy giao thức này cho các câu lệnh thú vị sẽ rất kỳ lạ và ngu ngốc, bởi vì nó đòi hỏi một khối lượng công việc khổng lồ phải thực hiện. Về lý thuyết, điều này là "hiệu quả" vì tổng chi phí chứng minh sẽ tăng đa thức theo kích thước của dữ liệu đầu vào, nhưng trên thực tế, nó sẽ hoàn toàn khác.

Vì vậy, cho đến nay chúng tôi chỉ cho thấy rằng bằng chứng đó khả thi. Việc tìm kiếm bằng chứng đủ thực tế để sử dụng trong thế giới thực là việc của chúng ta.

Trong các bài viết khác tôi sẽ nói về một số trong số đó - cụ thể là hiệu quả bằng chứng của các tuyên bố hữu ích khác nhau. Tôi sẽ đưa ra một số ví dụ (từ ứng dụng thực tế), nơi mà các kỹ thuật như vậy đã được sử dụng. Ngoài ra, theo yêu cầu của một độc giả, tôi sẽ cho bạn biết lý do tại sao tôi không thích giao thức SRP (Mật khẩu từ xa an toàn) đến vậy.

Ghi chú

* Về mặt hình thức, mục tiêu của bằng chứng tương tác là thuyết phục Người xác minh rằng một chuỗi cụ thể thuộc về một số ngôn ngữ. Thông thường, Prover rất mạnh (không giới hạn) và Người xác minh bị hạn chế về tài nguyên máy tính.

** Ví dụ này dựa trên giải pháp ban đầu của Goldwasser, Micali và Rekoff, và ví dụ hướng dẫn về mũ dựa trên giải thích của Silvio Micali. Tôi chỉ chịu trách nhiệm về những sai sót nếu có.

*** Một ví dụ đơn giản về cam kết có thể được xây dựng bằng hàm băm. Để tạo cam kết cho giá trị "x", chỉ cần tạo một số chuỗi số ngẫu nhiên (đủ dài), chúng tôi sẽ gọi là "muối" và in cam kết C = Băm(muối || x) . Để công khai cam kết, bạn chỉ cần hiển thị dấu "x" và muối. Bất cứ ai cũng có thể xác minh rằng cam kết ban đầu là hợp lệ bằng cách tính toán lại hàm băm. Sẽ an toàn miễn là đáp ứng được một số yêu cầu (nghiêm ngặt vừa phải) đối với chính chức năng đó.

Matthew xanh