Trong khi đọc các hướng dẫn về tính toán hai bên, tôi đã gặp hai định nghĩa khác nhau (ít nhất là chính thức) về bảo mật (với các đối thủ nửa trung thực).
Điều tôi muốn biết là liệu những định nghĩa này thực sự khác nhau hay có thể được chứng minh là tương đương.
Tôi nghi ngờ rằng chúng khác nhau, nhưng tôi có thể thiếu điều gì đó, vì tôi chưa đọc ở đâu về các định nghĩa khác nhau.
Trong Lindell (2016), tính toán an toàn của hai bên được định nghĩa như sau:
Đối với mỗi bên, phân phối chung của mô phỏng và kết quả lý tưởng phải không thể phân biệt về mặt tính toán với phân phối chung của chế độ xem đối nghịch và đầu ra được tính toán.
Về mặt hình thức, đối với mỗi $i \in \{1, 2\}$, phải tồn tại p.p.t. thuật toán $S_i$ như vậy mà
$$
{\lbrace (S_i(1^n, x, f_1(x, y)), f(x, y)) \rbrace}_{x, y, n}
\stackrel{c}{\equiv}
{\lbrace (\operatorname{view}^\pi_i(x, y, n), \operatorname{output}^\pi_i(x, y, n)) \rbrace}_{x, y, n}
\,\chữ{.}
$$
Định nghĩa này có ý nghĩa với tôi, vì tác giả định nghĩa không thể phân biệt tính toán vượt quá xác suất tập hợp được lập chỉ mục bởi cả tham số bảo mật và đầu vào:
Hai tổ hợp xác suất $X = \{X(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ và $Y = \{Y(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ được cho là không thể phân biệt về mặt tính toán, được biểu thị bằng $X \stackrel{c}{\equiv} Y$, nếu với mọi thuật toán thời gian đa thức không đồng nhất $D$ tồn tại một chức năng không đáng kể $\mu(\cdot)$ sao cho mọi $a \in \{0, 1\}^*$ và mọi thứ $n \in \mathbb{N}$,
$$
\lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n)
\,\chữ{.}
$$
Điều này có nghĩa là phải có một chức năng không đáng kể duy nhất $\mu$ cho tất cả các đầu vào quản lý an ninh.
Ngược lại, Evans và cộng sự. (2018) xác định khả năng không thể phân biệt tính toán cho các nhóm xác suất chỉ được lập chỉ mục bởi tham số bảo mật.
Tôi cũng đã thấy các định nghĩa về tính không thể phân biệt bằng máy tính như thế này ở những nơi khác.
Sau đó, khi xác định bảo mật, họ yêu cầu các bản phân phối chung không thể phân biệt được về mặt tính toán cho tất cả các đầu vào.
Ít nhất về mặt hình thức, điều này gợi ý cho tôi rằng ở đây, chức năng không đáng kể có thể phụ thuộc vào đầu vào.
Câu trả lời cho các câu hỏi sau đây sẽ được đánh giá rất cao:
- Tôi đang thiếu một cái gì đó hoặc hiểu sai các định nghĩa? Các định nghĩa được hiển thị là tương đương có thể khai thác sự không đồng nhất của đối thủ không?
- Nếu không, có phải trong định nghĩa sau, không bắt buộc phải có một hàm không đáng kể duy nhất "hoạt động" cho tất cả các đầu vào?
Nếu tôi không nhầm thì điều đó có nghĩa là hai định nghĩa trên thực tế là khác nhau?
- Trong trường hợp chúng khác nhau: Định nghĩa nào nên được ưu tiên hơn?
