Cài đặt
Gần đây, tôi bắt đầu quan tâm đến bằng chứng dựa trên mô phỏng trong bối cảnh tính toán an toàn của hai bên. Tôi đọc một số chương sách (từ MPC an toàn và chia sẻ bí mật và Cơ sở về mật mã tập 2), giấy tờ (quan trọng nhất Làm thế nào để mô phỏng nó) và các bài đăng từ trao đổi ngăn xếp mật mã, nhưng tôi vẫn không cảm thấy tự tin trong việc áp dụng các kỹ thuật chứng minh dựa trên mô phỏng. Bước đầu tiên, tôi xem xét một cách đơn giản giao thức chia sẻ bí mật bổ sung với các bên bán trung thực. Ở đó, các bên muốn nhân rộng bí mật của họ và sử dụng bộ ba Beaver cho điều đó, sao cho giao thức liên quan đến một số tương tác. Tôi chia sẻ nó ở đây vì nó có thể hữu ích cho những người mới bắt đầu khác và tôi sẽ đánh giá rất cao những sửa chữa, phê bình và nhận xét.
giao thức nhân
Giả sử hai bên không thông đồng và giả sử đầu vào $x,y$ thuộc về các bên $P_1,P_2$, tương ứng. Sau đó, $P_1$ tính toán cổ phần $x_1\leftarrow \mathbb{Z}_q$, $x_2 = x-x_1\,\mathrm{mod}\,q$, ở đâu $\leftarrow \mathbb{Z}_q$ biểu thị lấy mẫu ngẫu nhiên thống nhất từ $\mathbb{Z}_q$, và gửi $x_2$ đến $P_2$. Điều tương tự xảy ra tương tự với $y_1,y_2$ tại $P_2$ như vậy mà $P_1$ có quyền truy cập vào $x_1,y_1$ và $P_2$ có quyền truy cập vào $x_2,y_2$ sau bước này. để tính toán $xy$, các bên sử dụng bộ ba Beaver như sau. Trước khi thực hiện giao thức, chúng tôi lấy mẫu $(\alpha,\beta)\leftarrow \mathbb{Z}_q^2$, tính toán $\alpha \beta \,\mathrm{mod}\,q = \gamma$ cũng như cổ phần $\alpha_i,\beta_i,\gamma_i$ với $i\in\{1,2\}$và phân phối chúng cho bên tương ứng. Sau đó, $i$-th bên tính toán
\begin{align*}
\delta_i=x_i-\alpha_i\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon_i=y_i-\beta_i\,\mathrm{mod}\,q
\end{align*}
và gửi $\delta_i$ cũng như $\epsilon_i$ sang bên kia. Kết quả là, cả hai bên có thể tính toán
$$
\delta=\delta_1+\delta_2\,\mathrm{mod}\,q=x-\alpha\,\mathrm{mod}\,q \quad \text{and} \quad \epsilon=\epsilon_1+\epsilon_2\, \mathrm{mod}\,q=y-\beta\,\mathrm{mod}\,q.
$$
Với những thứ này trong tay, cuối cùng người ta có được cổ phần của $z:=z_1+z_2\,\mathrm{mod}\,q$ bằng phương tiện của
\begin{align*}
z_1=\gamma_1+\delta \beta_1 +\epsilon \alpha_1+\delta\epsilon\,\mathrm{mod}\,q \quad \text{and} \quad
z_2=\gamma_2+\delta \beta_2+\epsilon \alpha_2\,\mathrm{mod}\,q.
\end{align*}
chúng tôi không tiết lộ $z_1$ hoặc $z_2$ (mặc dù giao thức có vẻ vô dụng theo cách này).
Lưu ý rằng $x_2,y_1,\delta_1,\delta_2,\epsilon_1,\epsilon_2$ đã được trao đổi và tất cả các đại lượng này là các số ngẫu nhiên thống nhất trong $\mathbb{Z}_q$. Tất cả các tính toán khác là cục bộ. Từ đó, tôi kết luận rằng giao thức phải được bảo mật tuyệt đối.
Bằng chứng dựa trên mô phỏng (thử)
Theo như tôi hiểu, các bằng chứng dựa trên mô phỏng đặc biệt hấp dẫn đối với các giao thức, trong đó ngoài mã hóa, tính toán và trao đổi dữ liệu có thể tiết lộ điều gì đó. Do đó, nó phải phù hợp với giao thức được chỉ định ở trên.
Hãy thử chứng minh trực giác đã nói ở trên (rằng giao thức hoàn toàn an toàn) một cách chính thức hơn bằng cách áp dụng những gì có thể tìm thấy trong Làm thế nào để mô phỏng nó và MPC an toàn và chia sẻ bí mật. Đầu tiên, chúng tôi quan sát thấy rằng giao thức (gần như) đối xứng.Do đó, sẽ là đủ nếu chúng ta chỉ xem xét $P_1$ là nửa trung thực. Tiếp theo, chức năng $f(x,y):=z$ của giao thức $\pi$ là tất định và thỏa mãn tính đúng đắn (đánh giá $z_1+z_2\,\mathrm{mod}\,q$ để xác minh). Hơn nữa, thành phần đầu tiên của $f(x,y)$ Là $f_1(x,y):=z_1$ và chúng tôi giới thiệu quan điểm của $P_1$ qua
\begin{align*}
\mathrm{view}_1^{\pi}(x,y):=\left(x,r_1,m_1,m_2,\dots,m_t\right)\in \mathbb{Z}_q^{1\times p },
\end{align*}
ở đâu $r_1$ là nội dung của $P_1$băng ngẫu nhiên bên trong, và $m_1,m_2,\dots,m_t$ biểu thị các tin nhắn nhận được.
Sau đó, một bằng chứng dựa trên mô phỏng để bảo mật hoàn hảo yêu cầu tồn tại một trình mô phỏng thời gian đa thức xác suất $S_1$ như vậy mà
\begin{align*}
\{S_1\left(x,f_1(x,y)\right)\}_{x,y\in\{0,1\}^*} \stackrel{\mathrm{perf}}{\equiv} \ {\mathrm{view}_1^{\pi}\left(x,y\right)\}_{x,y\in\{0,1\}^*}.
\end{align*}
Cần đạt được sự không thể phân biệt hoàn hảo giữa các tổ hợp xác suất này nếu có thể $x,y\in\{0,1\}^*$ khoảng cách thống kê
\begin{phương trình}
\nhãn{eq:dist}
\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y)):=\frac{1}{2} \sum_{\boldsymbol{w}\in\ mathbb{Z}_q^{1\times p}} |\mathrm{Pr}(\mathrm{view}_1^{\pi}(x,y)=\boldsymbol{w})-\mathrm{Pr}( S_1(x,f_1(x,y)=\boldsymbol{w})|
\end{phương trình}
biến mất. Chúng tôi bắt đầu bằng cách chạy $\pi$ và, theo định nghĩa từ trước, tìm
$$
\mathrm{view}_1^{\pi}\left(x,y\right)=\left(x,x_1,y_1,\alpha_1,\beta_1,\gamma_1,\delta_2,\epsilon_2\right),
$$
ở đâu $x_1$ bắt nguồn từ $P_1$nguồn ngẫu nhiên bên trong của nó (cuốn băng ngẫu nhiên), $\alpha_1,\beta_1,\gamma_1$ xuất phát từ một nguồn ngẫu nhiên ngoại tuyến phụ trợ (nhưng cũng có thể được coi là tin nhắn?), và $y_1,\delta_2,\epsilon_2$ là tin nhắn nhận được từ $P_2$. Lưu ý rằng ngoài $x$ tất cả các đại lượng này là ngẫu nhiên thống nhất trong $\mathbb{Z}_q$. Hơn nữa, từ $\mathrm{view}_1^{\pi}(x,y)$ tất cả các đại lượng khác, mà $P_1$ có quyền truy cập, có thể được tính toán. Vì thế, $\mathrm{view}_1^{\pi}(x,y)$ chứa tất cả $P_1$thông tin của.
Nó vẫn còn để tìm một phù hợp $S_1$. Để kết thúc này, chúng tôi chọn
$$
S_1(x,f_1(x,y))=\left(x,\dấu ngã{x}_1,\dấu ngã{y_1},\dấu ngã{\alpha}_1,\dấu ngã{\beta}_1,\dấu ngã{\ gamma}_1,\tilde{\delta}_2,\tilde{\epsilon}_2\right)
$$
sao cho mỗi thành phần trong $(\tilde{x}_1,\tilde{y_1},\tilde{\alpha}_1,\tilde{\beta}_1,\tilde{\gamma}_1,\tilde{\delta}_2,\tilde{ \epsilon}_2)$ là ngẫu nhiên thống nhất trong $\mathbb{Z}_q$ (có vẻ như chúng ta không cần đầu ra $f_1(x,y)$). Cuối cùng, kể từ khi $S_1$ có thể bắt chước chính xác các bản phân phối của từng thành phần trong $\mathrm{view}_1^\pi$, dễ thấy rằng $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))=0$ cho tất cả $x,y$. Nói cách khác, mọi thứ ngoài $x$ (được cấp cho $P_1$) không thể phân biệt được với rác ngẫu nhiên. Do đó, chúng tôi kết luận rằng giao thức này hoàn toàn an toàn.
Một số quan sát / câu hỏi
- Trong bối cảnh tính toán hai bên an toàn, có vẻ như bất cứ khi nào $\mathrm{view}_1^\pi$ chỉ chứa các biến ngẫu nhiên (ngoại trừ $x$), chúng ta có thể xây dựng một trình mô phỏng đơn giản bằng cách chọn các biến có cùng phân phối như các biến ngẫu nhiên. Điều này làm cho việc xây dựng giả lập trở nên tầm thường.
- Trong trường hợp, một biến trong $\mathrm{view}_1^\pi$ hoạt động không ngẫu nhiên, chúng ta phải xây dựng nó từ $x,f_1(x,y)$ để có được một mô phỏng hợp lệ. Để đạt được điều này, giả sử $y_1=y$ bởi vì $P_2$ mắc lỗi. Rõ ràng, điều này không an toàn vì $P_1$ hiện có quyền truy cập vào $x,y$. Tuy nhiên, chỉ từ $x,f_1(x,y)$ chúng ta không thể xây dựng $y$ bởi vì $x$ không có gì để làm với $y$ và $f_1(x,y)$ là ngẫu nhiên thống nhất trong $\mathbb{Z}_q$ bằng xây dựng. Vì vậy, giao thức này không an toàn do $\Delta(\mathrm{view}_1^\pi(x,y),S_1(x,f_1(x,y))\neq 0$.
- lý do mà trình giả lập cần là gì $f_1(x,y)$?
