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
- Tính đầy đủ: đã cho $x \in L$, $B$ chấp nhận với xác suất rất cao;
- Âm thanh: đưa ra bất kỳ câu tục ngữ nào $A'$ và $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;
- 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$ và $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$ và $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.