Điểm:1

Các hệ thống bằng chứng không kiến ​​thức tương tác có thể được triển khai bằng tính toán an toàn của hai bên không?

lá cờ sa

Tôi đang xác định tính toán đa bên bằng cách sử dụng mô hình thực-lý tưởng (xem Giới thiệu thực tế về tính toán đa bên an toàn). Nghĩa là, đối với bất kỳ cuộc tấn công thành công nào vào giao thức MPC trong thế giới thực, tồn tại một trình mô phỏng thực hiện cuộc tấn công này thành công trong thế giới lý tưởng. Theo đó, bảo mật trong thế giới thực phải tương đương với bảo mật trong thế giới lý tưởng.

Tôi đang xác định các hệ thống bằng chứng không kiến ​​thức tương tác cho một ngôn ngữ $L$ sử dụng định nghĩa ban đầu từ Sự phức tạp về kiến ​​thức của các hệ thống bằng chứng tương tác. Tức là một cặp $(A, B)$ của các máy Turing tương tác phải đáp ứng

  1. Tính đầy đủ: đã cho $x \in L$, $B$ chấp nhận với xác suất rất cao;
  2. Âm thanh: đưa ra bất kỳ câu tục ngữ nào $A'$$x \không\trong L$ vượt qua $(A', B)$, $B$ chấp nhận với xác suất rất thấp;
  3. Zero-Knowledge: tồn tại một trình giả lập thời gian đa thức xác suất có thể mô phỏng toàn bộ quá trình trao đổi thông điệp giữa $A$$B$ cho bất kỳ đầu vào $x \in L$.

Bây giờ, tờ báo Kiến thức không từ tính toán nhiều bên an toàn đề cập đến những điều sau đây:

Các giao thức không kiến ​​thức có thể được xem như một trường hợp đặc biệt của bảo mật hai bên tính toán, trong đó chức năng xác minh tính hợp lệ của một nhân chứng do người hoạt ngôn nắm giữ.

Đó là, đưa ra $L \in \mathcal{NP}$, tồn tại một thuật toán $A$ như vậy mà $x \in L \iff \exists w\dấu hai chấm A(x, w) = 1$ (định nghĩa của $\mathcal{NP}$). Một bữa tiệc $P_1$ đóng vai trò là người chứng minh, khác $P_2$ với tư cách là người xác minh. $P_1$ biết $x$$w$, $P_2$ chỉ biết $x$. Họ thực hiện $A(x, w)$ với nhau để xác định xem $x \in L$ hay không.

Thông suốt, $w$ không được tiết lộ cho người xác minh $P_2$ do giao thức MPC. Tuy nhiên, định nghĩa về kiến ​​​​thức không tổng quát hơn phải không? Nếu người tục ngữ $P_1$ đã gửi, vì một số lý do, giải pháp cho một số trường hợp của một $\mathcal{NP}$-hoàn thành bài toán1, không có trình mô phỏng thời gian đa thức nào có thể mô phỏng giả định này $\mathcal{P} \neq \mathcal{NP}$. Hệ thống bằng chứng được tạo ra sẽ không phải là không có kiến ​​thức.

Vì vậy, do giao thức MPC có thể trao đổi các thông báo không thể mô phỏng, giao thức MPC thực sự không thể được sử dụng để triển khai hệ thống bằng chứng không có kiến ​​thức cho một số ngôn ngữ $L \in \mathcal{NP}$, được không?


1 Giải pháp có thể được thực hiện phụ thuộc vào $x$ sao cho nó không phải là hằng số và do đó có thể mô phỏng dễ dàng.

Điểm:2
lá cờ cn

Kiến thức không ban đầu được xác định đối với các câu tục ngữ tùy ý (có thể không bị ràng buộc). Tuy nhiên, khi chúng tôi sử dụng hoặc thảo luận về kiến ​​thức bằng không trong mật mã, chúng tôi hầu như luôn ngầm giả định ZK cho NP trong đó trình tục ngữ chạy trong thời gian đa thức được đưa ra bằng chứng cho tuyên bố. Đây là loại bằng chứng không có kiến ​​thức mà bài báo đã đề cập đến và đây thực sự là một trường hợp đặc biệt của tính toán hai bên an toàn độc hại.

cadaniluk avatar
lá cờ sa
Có, nhưng kế hoạch này là những gì tôi đã mô tả ngay bên dưới trích dẫn với các bên $P_1$ và $P_2$, phải không? Câu hỏi của tôi giải quyết cụ thể rằng kiến ​​thức không có nghĩa là không những không rò rỉ $w$, mà còn không rò rỉ bất kỳ thứ gì khác, trong khi MPC an toàn có thể rò rỉ kiến ​​thức khác ngoài $w$. Do đó, tôi thấy không hợp lý khi MPC có thể được sử dụng để xây dựng bằng chứng không kiến ​​thức.
Geoffroy Couteau avatar
lá cờ cn
Làm thế nào mà người chứng minh thời gian đa thức (người chỉ được làm nhân chứng cho tuyên bố) tiết lộ "kiến thức khác" này? Điều này được mã hóa cứng trong mô tả của nó - sau đó nó có thể được mã hóa trong trình giả lập hoặc dễ dàng tính toán (sau đó trình giả lập có thể tính toán nó). Mặt khác, không có cách nào bất cứ thứ gì khó mô phỏng bị rò rỉ bởi giao thức MPC. Nếu bạn kiểm tra định nghĩa, nó sẽ trực tiếp khẳng định rằng MPC 2 bên độc hại là sự tổng quát hóa nghiêm ngặt của kiến ​​thức bằng không.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.