Tôi sẽ cố gắng xác định dễ dàng hệ thống mật mã của bài báo này. Tác giả thiết kế một trò chơi giao tiếp cho $N$ người chơi. Thông tin cá nhân của mỗi người chơi được ký hiệu là $t_i\trong T_i$ và đại diện cho loại người chơi $i$. Hệ thống mã hóa mà người chơi sử dụng để liên lạc dựa trên các thư từ báo cáo sau đây.
$\textbf{Báo cáo thư từ:}$ Để cho $\mathcal{R}_i$ là một tập hợp không rỗng, hữu hạn và xác định sự tương ứng báo cáo $R_i : T_i\to 2^{\mathcal{R}_i}-\{\emptyset\}$ là một ánh xạ từ người chơi $i$âs nhập không gian vào tập hợp các tập hợp con của $\mathcal{R}_i$. Một yếu tố $r\in\mathcal{R}_i$ được gọi là một thông báo phụ thuộc vào loại và $R_i(t_i)$ là tập hợp các thông báo phụ thuộc vào loại có sẵn để nhập $t_i$ của người chơi $i$. Thông báo phụ thuộc vào loại xác nhận tuyên bố của người chơi về loại của anh ta. Ví dụ, nếu $S\trong T_i$ là tập hợp các loại người chơi $i$ ai có thể gửi tin nhắn $r\in R_i$, sau đó $r$ xác nhận một tuyên bố thuộc loại âloại của tôi nằm trong $S$â. Bộ $S$ do đó được gọi là một sự kiện có thể chứng nhận.
$\textbf{Cấu hình chứng nhận:}$ Để cho $E_i\subseteq 2^{T_i}-\{\emptyset\}$ là một tập hợp các tập hợp con của $T_i$ đó là đóng cửa dưới giao lộ. Một cấu hình chứng nhận là một $N$-tuple các thư từ báo cáo cụ thể $C_i:T_i\đến E_i$ Cho mọi $i = 1, ..., N$, với
$$C_i(t_i)=\{e_i\in E_i|t_i\in e_i\},\quad\text{$\forall t_i\in T_i$} $$
Những thư từ báo cáo này có hai thuộc tính rất hữu ích. Đầu tiên, mỗi thông báo giống hệt với sự kiện mà nó xác nhận. Thứ hai, bất kỳ sự kiện nào có thể chứng nhận bằng sự kết hợp của các thông báo trong $C_i(t_i)$ cũng được bao gồm trong bộ.
Để cho $R=(R_i)_{i\in I}$ là một hồ sơ tùy ý về các thư từ báo cáo và cho mọi người chơi $i\in I$, để cho $E_i^R$ biểu thị tập hợp nhỏ nhất có chứa $\{R^{-1}(r_i)|r_i\in \mathcal{R}_i\}$ andd bị đóng dưới giao lộ. $E_i^R$ là tập hợp tất cả các sự kiện mà người chơi $i$ có thể chứng nhận với $R_i$. hồ sơ $R$ có thể được liên kết duy nhất với cấu hình chứng nhận $C_R=(C_i^R)_{i\in I}$, ở đâu
$$C_i^R(t_i)=\{e_i\in E_i^R|t_i\in e_i\}$$
Cấu hình chứng nhận $C_i^R$ của $R$ thể hiện rõ ràng thông tin có thể chứng nhận dưới dạng các sự kiện trong không gian loại của người chơi.
$\textbf{Mã hóa:}$ Để cho $C=(C_i)_{i\in I}$ là một cấu hình chứng nhận. Nếu thông tin có thể kiểm chứng được mã hóa, cứ mỗi $i\in I$, mọi sự kiện có thể chứng nhận $e_i\in E_i$ được mã hóa bằng thuật toán mật mã, được gọi là mật mã. Mật mã là một ánh xạ $Ï_i: E_i à Y_i â X_i$ có đầu vào là thông tin cá nhân $e_i$ và một phần thông tin bổ sung $y_i\trong Y_i$, được gọi là khóa và tạo đầu ra là mã $x_i\trong X_i$. Người ta cho rằng bộ khóa $Y_i$ đủ lớn, tức là $|Y_i| ⥠|E_i|$, và điều đó cho mỗi $y_i\trong Y_i$ ánh xạ $Ï(\cdot, y_i)$ là dự cảm, do đó mọi cặp $(x_i, y_i)$ được liên kết với chính xác một sự kiện có thể chứng nhận $e_i$. Khi thông tin của một người chơi được mã hóa, các thông báo phụ thuộc vào loại của anh ta là các cặp bao gồm một đoạn mã và một khóa. Vào thời điểm người chơi tìm hiểu loại của họ, tự nhiên chọn mật mã công khai $Ï_i$ cho người chơi $i\in I$ và một khóa riêng $y_i$ thống nhất từ tập hợp
$Y_i$. Người chơi $i$âs báo cáo tương ứng sau đó được đưa ra bởi
$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=Ï_i(e_i, y_i), e_i\in C_i(t_i)\}$$
Một giải thích tự nhiên của các thông điệp trong $R_i$ là những mẩu bằng chứng được mã hóa liên quan đến người chơi $i$â loại, được cung cấp bởi bên thứ ba đáng tin cậy sử dụng mật mã đã biết công khai và khóa riêng để mã hóa thông tin. Lưu ý rằng nếu $C=C^R$, sau đó các cấu hình $R(\cdot)=(R_i(\cdot))_{i\in I}$ và $\hat{R}(\cdot,y)=(\hat{R}_i(\cdot,y_i))_{i\in I}$ có cấu hình chứng nhận chung cho mọi tổ hợp phím $y\in(Y_i)_{i\in I}$
Để cho $E^R=(E_i^R)_{i\in I}$ là hồ sơ của tập hợp các sự kiện có thể chứng nhận được với $R$. Bộ $E_i^R$ là hữu hạn, do đó tất cả các phần tử của nó có thể được gán nhãn theo thứ tự tùy ý với chỉ số từ $1$ đến một số nguyên dương $n_i$. Sau đó, mỗi sự kiện có thể chứng nhận có thể được liên kết với chỉ mục của nó, tức là một số trong tập hợp $\{1,...,n_i\}$. tôi sẽ viết $z_i(e_i)$ để chỉ số đại diện cho sự kiện $e_i$ và, hơi lạm dụng ký hiệu, tôi sẽ viết $e_i(z_i)$ để chỉ sự kiện có chỉ số bằng $z_i$.
Bổ đề sau là cần thiết
$\textbf{Bổ đề:}$ Nếu $z_i$ là một biến ngẫu nhiên có hỗ trợ trên $\{1,...,n_i\}$ và $y_i$ được phân bố đều trên $\{1,...,n_i\}$ độc lập khỏi $z_i$, thì biến ngẫu nhiên $x_i$ Được định nghĩa bởi $x_i=z_iây_i(mod{n}_i)$ cũng được phân bố đều trên $\{1,...,n_i\}$.
Đây, $z_i$ đại diện cho một sự kiện có thể chứng nhận, $y_i$ đại diện cho một chìa khóa, và $x_i$ là mã được tạo bởi mật mã $Ï_i(e_i,y_i)=z_i(e_i)ây_i(mod{n}_i)$. Bây giờ, giả sử người chơi $i$– thông tin cá nhân của anh ấy được mã hóa và thư từ báo cáo của anh ấy được
$$\hat{R}_i(t_i,y_i)=\{(x_i, y_i)|x_i=z_i(e_i)ây_i(mod{n}_i), e_i\in C_i(t_i)\}$ $
vì vậy người chơi đó $i$ có thể gửi một cặp $(x_i,y_i)$ nếu sự kiện $e_i$ đại diện bởi $z_i=x_i+y_i(mod{n}i)$ trong $C_i^R(t_i)$. Cấu hình chứng nhận được tạo theo cách này
giống hệt với cấu hình chứng nhận của $R$: nếu chỉ loại người chơi $i$ ai có thể chứng nhận $e_i$ với $R_i$ có thể gửi một cặp $(x_i, y_i)$ thỏa mãn $z_i=x_i+y_i(mod{n}_i)$, sau đó gửi một cặp như vậy giống như xác nhận $e_i$. Theo bổ đề $1$, cả hai $x_i$ và $y_i$ được phân bố đều trên $\{1,...,n_i\}$, và do đó, riêng lẻ, $x_i$ và $y_i$ không chứa thông tin về $e_i$.
$\textbf{Câu hỏi:}$ Nếu chúng ta giả sử rằng trong trường hợp cấu trúc toán học ở trên, mật mã được định nghĩa là nhị từ trong đó mọi cặp $(x_i,y_i)$ đề cập đến một phương trình tuyến tính sao cho $h(x)=ax+b$, $b=e_i$. Nếu hai người chơi biết $(x_i,y_i)$ có thể kết hợp chúng và lấy những gì nó bỏ lỡ cho chúng để $x_i+y_i(nod{n}_i)=z_i(e_i)\quad\text{or $e_i(z_i)$}$. Do đó trong trường hợp chúng ta lấy $h$ đa thức bậc $t<2N$ như vậy mà
$$h(x)=a_tx^t+a_{t-1}x^{t-1}+\cdots+a_1x+a_0,\quad\text{where $a_0=e_i(z_i)$}$$
đại diện tương đương của là gì $\rho_i$, nơi biết họ là cần thiết $t+1$ cặp để tính toán $h(x)$ với thời hạn không đổi $e_i(z_i)$ (về bản chất có nghĩa là $t+1$ đôi $(x_i,y_i)$ được liên kết với chỉ một $e_i$ (trắc nghiệm))?
Nói cách khác, câu hỏi thay đổi thành câu hỏi tương đương có nội dung: "Ai có thể giúp biểu diễn đa thức đơn giản của mật mã $\rho_i$"?
$\textbf{Gợi ý:}$ Với một chút lạm dụng ký hiệu, tôi nghĩ rằng tác giả sử dụng $\{1,...,n_i\}$ thay vì $\{0,1,...,n_i-1\}$.
