完美安全两方计算与基于hCLWE的公钥加密方案

### 完美安全两方计算与基于hCLWE的公钥加密方案 #### 完美安全两方计算 在两方计算中，我们关注的是如何让两个参与方在不泄露各自输入的情况下，共同计算一个函数。这里主要探讨了完美安全的两方计算，特别是针对四输出功能的情况。 ##### 四输出功能的不可能结果 对于一个确定性对称的两方四输出功能 $f : X × Y \to \{0, 1, 2, 3\}$，如果它能在CR混合模型中以完美安全的方式计算，那么它要么是螺旋函数，要么是透明传输函数。为了证明这一点，我们从一个通用的不可能结果（Lemma 4）出发。 - **Corollary 6**：如果存在一个 $2×2$ 矩形 $R$，其对应的子矩阵 $M_R^f$ 是禁止的（见Definition 12），那么 $f$ 不能在CR混合模型中以完美安全的方式计算。 - **Corollary 7**：如果 $f$ 能在CR混合模型中以完美安全的方式计算，那么任何 $2 × 2$ 矩形 $R \subseteq X × Y$ 诱导的子矩阵有以下几种形式： - $M_R^f \sim \begin{pmatrix}a & a \\ a & a\end{pmatrix}$ - $M_R^f \sim \begin{pmatrix}a & a \\ b & b\end{pmatrix}$ - $M_R^f \sim \begin{pmatrix}a & a \\ b & c\end{pmatrix}$ - $M_R^f \sim \begin{pmatrix}a & b \\ c & d\end{pmatrix}$ 其中 $a, b, c$ 和 $d$ 表示 $Z$ 中的不同元素。 接下来证明Lemma 2，它给出了一个两方四输出对称确定性功能 $f : X × Y \to \{a, b, c, d\}$ 能在CR混合模型中以完美安全的方式计算的必要条件。这基于以下两个声明： - **Claim 8**：如果 $M_f$ 包含一个 $2×2$ 子矩阵 $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$，其中 $\{a, b, c, d\} = \{0, 1, 2, 3\}$，那么 $f$ 是透明传输功能。 - **Claim 9**：如果 $M_f$ 中没有禁止的 $2×2$ 子矩阵，也没有形式为 $\begin{pmatrix}a & b \\ c & d\end{pmatrix}$（其中 $\{a, b, c, d\} = \{0, 1, 2, 3\}$）的子矩阵，那么 $f$ 是螺旋功能。 下面是Claim 8的证明过程： 假设存在一个 $2×2$ 矩形 $R = \{x_1, x_2\}×\{y_1, y_2\}$，使得 $M_R^f = \begin{pmatrix}a & b \\ c & d\end{pmatrix}$。考虑取 $Z_R = \{a, d\}$，由于 $M_R^f$ 中每行和每列都恰好包含一个 $Z_R$ 中的元素，且子矩阵包含一个 $Z\setminus Z_R$ 中的元素，所以Lemma 4中的Item 1成立。因为 $f$ 能在CR混合模型中以完美安全的方式计算，根据Lemma 4，至少有以下情况之一成立： - 存在一行 $x_3 \in X\setminus\{x_1, x_2\}$，使得 $\{M_f(x_3, y_1), M_f(x_3, y_2)\} = \{a, d\}$。若 $M_f(x_3, y_1) = d$ 且 $M_f(x_3, y_2) = a$，会得到一个禁止的子矩阵，与假设矛盾，所以 $(M_f(x_3, y_1), M_f(x_3, y_2)) = (a, d)$。 - 存在一列 $y_3 \in Y\setminus\{y_1, y_2\}$，使得 $\{M_f(x_1, y_3), M_f(x_2, y_3)\} = \{a, d\}$。同理，$(M_f(x_1, y_3), M_f(x_2, y_3)) = (a, d)$。 取 $Z_R = \{b, c\}$ 并使用类似的论证，至少有以下情况之一成立： - 存在一行 $x_4 \in X\setminus\{x_1, x_2\}$，使得 $(M_f(x_4, y_1), M_f(x_4, y_2)) = (c, b)$。 - 存在一列 $y_3 \in Y\setminus\{y_1, y_2\}$，使得 $(M_f(x_1, y_4), M_f(x_2, y_4)) = (b, c)$。 由此可知，$M_f$ 中必有以下子矩阵之一： $\begin{pmatrix}a & b \\ c & d \\ a & d