安全非交互式可约性的可判定性解析

### 安全非交互式可约性的可判定性解析 #### 1. 预备知识 在深入探讨安全非交互式可约性（SNIR）之前，我们需要了解一些基础的符号和概念。 - **符号表示** - 用 $[n]$ 表示集合 $\{1, \cdots, n\}$，用 $\langle n \rangle$ 表示集合 $\{0, \cdots, n - 1\}$。 - $R$ 代表实数集，本文中定义的集合均为有限集，通常用 $X$、$Y$ 等表示集合，集合 $X$ 中的元素用 $x$ 表示。 - 向量和矩阵由有限集的元素索引。对于集合 $X$，$v \in R^X$ 表示 $v$ 是一个列向量，其元素为以 $X$ 中元素为索引的实数，常称 $v$ 为 $X$ 维向量，$v$ 在位置 $x$ 的元素记为 $(v)_x$，简化为 $v_x$。对于集合 $X$ 和 $Y$，$H \in R^{X \times Y}$ 表示 $H$ 是一个 $X \times Y$ 维矩阵，$H$ 的第 $x$ 行和第 $y$ 列分别记为 $(H)_{(x, \cdot)}$ 和 $(H)_{(\cdot, y)}$，简化为 $H_{(x, \cdot)}$ 和 $H_{(\cdot, y)}$，元素 $(H)_{(x, y)}$ 简化为 $H_{(x, y)}$。矩阵的转置记为 $H^{\top}$，$|H|$ 表示 $H$ 的绝对值矩阵，即 $(|H|)_{(i, j)} = |(H)_{(i, j)}|$。 - 所有元素为 1（或 0）的 $X$ 维列向量记为 $1_X$（或 $0_X$）。对于 $x \in X$，$\xi^X_x$ 表示沿 “方向 $x$” 的 $X$ 维单位向量，即 $(\xi^X_x)_x = 1$ 且 $(\xi^X_x)_{x'} = 0$（$x' \neq x$），当维度明确时可省略上标。 - 用 $O_D(\epsilon)$ 表示形如 $f(D) \cdot \epsilon$ 的上界，其中 $f$ 是固定的非负函数。 - **概率相关** - 本文只考虑有限集上的分布。集合 $X$ 上的分布由分布向量 $\pi \in R^X_{\geq 0}$ 完全描述，满足 $\sum_{x \in X} \pi_x = 1$，$x \in X$ 的概率为 $\pi_x$。独立于所有先前定义的随机变量，按照分布 $\pi$ 采样 $x$ 记为 $x \sim \pi$。两个分布 $\pi$ 和 $\pi'$ 在同一集合 $X$ 上的统计距离或总变差距离记为 $SD(\pi, \pi')$，计算公式为 $SD(\pi, \pi') = \frac{1}{2} \sum_{x \in X} |\pi_x - \pi'_x|$。 - **相关性** - 相关性是两个有限集乘积上的联合分布。$X \times Y$ 上的相关性由联合分布矩阵 $H \in R^{X \times Y}_{\geq 0}$ 完全描述，满足 $\sum_{x \in X} \sum_{y \in Y} H_{(x, y)} = 1$。$H$ 的左边缘分布（即联合分布第一个坐标的边缘分布）由分布向量 $H1_Y$ 给出，右边缘分布由行向量 $1^{\top}_X H$ 或列向量 $H^{\top} 1_X$ 给出。记 $(X, Y) \sim H$ 表示随机变量 $(X, Y)$ 按照分布 $H$ 分布，即 $P_{X, Y}(x, y) = H_{(x, y)}$。当说 Alice 和 Bob 收到相关性 $(X, Y)$ 时，意味着 Alice 和 Bob 分别收到随机变量 $X$ 和 $Y$。非交互式安全约简的目标是让 Alice 和 Bob 使用手头的相关性（可能多个副本）在不相互通信的情况下安全地实现所需的相关性。 - **范数定义** - 对于 $X \times Y$ 维矩阵 $H$，1 - 范数 $\|H\|_{1, 1}$ 是 $H$ 中所有元素绝对值之和，即 $\|H\|_{1, 1} = \sum_{(x, y) \in X \times Y} |H_{(x, y)}| = (1_X)^{\top} |H| 1_Y$。 - $n$ 维向量 $v$ 的 2 - 范数定义为 $\|v\|_2 = (\sum_{i \in [n]} v^2_i)^{\frac{1}{2}}$。 - **随机矩阵** - 非负元素的矩阵 $H \in R^{X \times Y}_{\geq 0}$ 若满足 $H1_Y = 1_X$，则称为随机矩阵。每个元素为 0 或 1 的随机矩阵称为确定性随机矩阵或简称为确定性矩阵。 - **对角矩阵** - 对于向量 $v \in R^X$，定义 $diag(v) \in R^{X \times X}$ 为对角矩阵，$(diag(v))_{(x, x')} = \begin{cases} v_x, & \text{if } x = x' \\ 0, & \text{otherwise} \end{cases}$。对于 $H \in R^{X \times Y}$，定义 $\Delta_H$ 为 $Y \times Y$ 维对角矩阵，$\Delta_H = diag(1^{\top}_X H)$。 - **张量积** - 当 $G \in R^{X \times Y}$ 和 $H \in R^{R \times S}$ 时，$G$ 和 $H$ 的张量（Kronecker）积 $G \otimes H$ 是一个 $(X \times R) \times (Y \times S)$ 维矩阵，对于所有 $(x, r) \in X \times R$ 和 $(y, s) \in Y \times S$，有 $(G \otimes H)_{((x, r), (y, s))} = G_{(x, y)} \cdot H_{(r, s)}$。当 $G$ 和 $H$ 是联合分布矩阵时，乘积分布（即从分布 $G$ 和 $H$ 中独立抽取）的分布矩阵为 $G \otimes H$。$n$ 个独立同分布样本从分布矩阵为 $G$ 的相关性中抽取的分布由联合分布矩阵 $G^{\otimes n}$ 描述。还有矩阵乘法和张量积的恒等式：对于矩阵 $G$、$H$、$G'$、$H'$，有 $(GH) \otimes (G'H') = (G \otimes G')(H \otimes H')$，特别地，对于 $t \in N$，$(GH)^{\otimes t} = G^{\otimes t} H^{\otimes t}$。 - **冗余相关性** - 若存在不同的 $x, x' \in X$ 和 $c \in R_{\geq 0}$ 使得 $H_{(x, \cdot)} = c \cdot H_{(x', \cdot)}$，或存在 $y, y' \in Y$ 和 $c \in R_{\geq 0}$ 使得 $H_{(\cdot, y)} = c \cdot H_{(\cdot, y')}$，则称 $X \times Y$ 上的相关性 $H$ 是冗余的。非冗余分布的两个边缘分布都具有完全支撑。对于冗余相关性，其非冗余核心是通过将冗余符号（两边）合并到它们的等价类中得到的相关性。 - **共同信息** - 若存在函数 $f: X \to \{0, 1\}$ 和 $g: Y \to \{0, 1\}$，使得当 $(X, Y) \sim H$ 时，$P[f(X) = g(Y)] = 1$ 且 $0 < P[f(X) = 0] < 1$，则称 $X \times Y$ 上的相关性 $H$ 具有共同信息。$H$ 具有非零共同信息当且仅当存在 $\varnothing \subset X_0 \subset X$ 和 $\varnothing \subset Y_0 \subset Y$，$X_0 \times Y_0$ 和 $(X \setminus X_0) \times (Y \setminus Y_0)$ 上的联合分布矩阵 $H_0$ 和 $H_1$，以及 $0 < \alpha < 1$，使得 $H$ 可以写成 $H = \begin{bmatrix} \alpha H_0 & 0 \\ 0 & (1 - \alpha) H_1 \end{bmatrix}$。不允许这样分解的相关性称为无共同信息相关性。 #### 2. 广义傅里叶变换 设 $\pi \in R^{\Omega}_{\geq 0}$ 是有限集 $\Omega$ 上的分布，考虑赋范向量空间 $L^2(\Omega, \pi)$，其元素为 $v \in R^{\Omega}$，即由 $\Omega$ 索引的实值向量，等价于函数 $v: \Omega \to R$。两个向量 $u, v \in R^{\Omega}$ 的内积 $\langle u, v \rangle_{\pi}$ 定义为 $\langle u, v \rangle_{\pi} = \sum_{\omega \in \Omega} \pi_{\omega} \cdot u_{\omega} \cdot v_{\omega}$。 - **傅里叶基** - 向量集 $\{\gamma_{\alpha} \in R^{\Omega} : \alpha \in \langle |\Omega| \rangle\}$ 构成 $L^2(\Omega, \pi)$ 的傅里叶基需满足： - $\gamma_0$ 是常数函数，即 $\gamma_0 = 1_{\Omega}$。 - 对于所有 $\alpha \in \langle |\Omega| \rangle$，$\gamma_{\alpha}$ 是单位范数，即 $\langle \gamma_{\alpha}, \gamma_{\alpha} \rangle_{\pi} = 1$。 - 对于所有不同的 $\alpha, \alpha' \in \langle |\Omega| \rangle$，$\gamma_{\alpha}$