安全非交互可约性判定：理论突破与实际应用

### 安全非交互可约性判定：理论突破与实际应用 #### 1. 引言 安全非交互约简（SNIR）作为一个新兴且基础的密码学原语，处于信息论和密码学多个重要研究领域的交叉点。它是一种信息论安全的双方计算模型，利用相关随机性，无需任何通信，将安全计算的简约性发挥到极致。其非安全的对应概念——非交互模拟，在信息论和计算机科学领域已有半个世纪的丰富研究历史。此外，SNIR 还与密码学复杂性密切相关，有助于衡量函数在双方安全计算协议中所需相关样本的数量。 SNIR 的核心问题是判定是否存在从一个双方相关性到另一个的 SNIR。此前的研究针对特定的相关性对给出了答案，但普遍情况下该问题是否可判定仍未明确。本文通过结合 SNIR 的谱分析和新的“ junt 定理”变体，彻底解决了这一判定问题。 #### 2. 主要贡献 - **统计到完美安全的结果**：对于一对相关性 D 和 C，存在统计安全的 SNIR（可能是弱安全）当且仅当存在从 D 到 $C^{\otimes \ell}$ 的完美安全 SNIR，其中 $\ell$ 可以从 D 和 C 计算得出。为证明这一点，我们提出并证明了适用于“广义傅里叶变换”的新“ junt 定理”，该定理可能具有独立的研究价值。 - **SNIR 问题的可判定性**：基于上述结果，我们证明了 SNIR 问题是可判定的。 - **新的必要条件**：我们展示了如何利用统计到完美安全的结果，为 SNIR 的存在性获得新的组合必要条件。例如，我们可以排除从 OT 相关性到 Rabin OT 相关性的 SNIR，这是先前结果未涵盖的情况。 #### 3. 相关工作 SNIR 独立于两项并发工作中被定义，并在后续研究中得到进一步发展。此前的研究提出了使用统计到完美安全结果和傅里叶分析来证明该结果的思路，但仅限于两个特定的目标分布，且未涵盖弱安全概念。 与 SNIR 相关的概念还包括安全零通信约简（SZCR）和标准的（半诚实）安全约简（SR）。大致关系为：SNIR ⇒ SR ⇒ SZCR，即 SNIR 是比 SR 更强的原语，而 SR 又比 SZCR 更强。虽然每个函数都有到 OT 相关性的 SR，但 SNIR 不存在完全相关性。SNIR 和 SZCR 都旨在解决 SR 的下界问题，但方式不同。SNIR 的下界问题相对容易，可为培养新技术提供平台；而 SZCR 的下界问题在形式上更难，但可为解决 SR 的原始难题提供新思路。 #### 4. 技术概述 ##### 4.1 SNIR 回顾 SNIR 有多种视角： - **协议视角**：SNIR 是一种统计安全的双方计算协议，用于从 2 输出目标分布 D 采样，双方可访问源分布 C 的样本，但不能交换消息。 - **矩阵视角**：可以用一对随机“协议”矩阵 (A, B) 表示 Alice 和 Bob 的操作，以及一对“模拟”矩阵 (U, V) 来满足正确性和隐私条件。在完美安全的情况下，满足以下等式： - $A^{\top} C B = D$ - $A^{\top} C = D V$ - $C B = U^{\top} D$ 在统计安全的一般情况下，这些等式允许有一个可由消失量界定的加法（矩阵）误差项。 - **谱视角**：从 SNIR (A, B) 导出的一对矩阵 ($\tilde{A}$, $\tilde{B}$) 满足一组类似于原始安全条件的条件，这些条件与通过奇异值分解得到的矩阵相关。 ##### 4.2 统计到完美安全的证明步骤 1. **广义傅里叶变换**：从谱协议表征出发，我们发现乘以 $F_C$ 对应于“广义傅里叶变换”。因此，我们可以将 $\tilde{A}$ 的列解释为对矩阵 $\mathring{A} := A F_D^{-1}$ 的列应用广义傅里叶变换的结果。$\mathring{A}$ 的每一列可以看作一个函数 $a : X^n \to \mathbb{R}$，广义傅里叶变换将其表示为一组基函数的线性组合。 2. **近似度界**：利用谱协议条件，我们得到 $\mathring{A}$ 列的“近似度界”，即高阶基函数的贡献具有低“能量”。但该度界仅适用于与非零奇异值相关的列，我们将这些列组成的矩阵记为 $\check{A}$。 3. **Junt 定理应用**：我