任意联合分布下的安全非交互模拟研究

# 任意联合分布下的安全非交互模拟研究 ## 1. 引言 安全非交互模拟（SNIS）是伪相关生成器的信息论类比。在双方场景中，Alice和Bob从源分布的相关私有随机样本开始，通过非交互方式，利用约简函数将其转换为目标分布的样本。若该构造满足模拟安全条件，则为从源分布到目标分布的SNIS。 ### 1.1 SNIS的应用动机 安全计算协议常将计算和加密成本高的部分转移到离线过程，该过程成本高且生成结构化相关私有随机数。而一些低成本的相关私有随机源也能支持安全计算，因此自然的解决方案是将这些低成本的相关性非交互且安全地转换为安全计算协议中使用的相关性。 ### 1.2 SNIS的安全与速率定义 SNIS的不安全度ν(n)需满足以下三个条件： 1. **正确性**：输出样本的联合分布与目标分布在统计距离上ν(n) - 接近。 2. **抵御恶意Alice**：对于目标分布支持集中的任意(u, v)，在u′ = u且v′ = v的条件下，xn的分布与v ν(n) - 接近独立。 3. **抵御恶意Bob**：对于目标分布支持集中的任意(u, v)，在U′ = u且V′ = v的条件下，Yn的分布与u ν(n) - 接近独立。 生产速率R((U, V), (X, Y))是当n → ∞且ν(n) → 0时，所有可能约简族中可达到的最大m(n)/n的上确界。 ### 1.3 与其他原语的关系及额外动机 - 单向安全计算使用额外一轮通信将源分布样本转换为目标分布样本。 - 非交互相关蒸馏将SNIS限制为目标分布是独立硬币分布。 - SNIS是信息论中非交互联合分布模拟的密码学扩展。 ### 1.4 问题陈述 研究从任意源分布生成二元对称信道（BSS）和二元擦除信道（BES）目标噪声的SNIS的可行性和速率，并确定相应的最大速率安全构造。源分布可以是任意的，样本空间大小和边缘分布无特定要求。 ## 2. 结果概述 ### 2.1 任意源SNIS的可行性表征 存在高效算法判断从源(X, Y)到BSS/BES的统计安全SNIS是否可行。若SNIS的模拟误差小于c/n（c为合适正常数），可将约简函数修改为完美安全的SNIS，且这些完美安全的约简是布尔常数 - juntas，依赖常数个输入变量，因此可穷举搜索所有此类规范约简来确定SNIS是否可行。 在密码学背景下，该结果表明对于给定的源和目标，要么存在完美安全的SNIS，要么所有SNIS构造都不安全。 ### 2.2 任意源SNIS的速率估计 若SNIS可行，则具有正常数速率。可通过将(X, Y)⊗n的样本划分为固定大小的块，对每个块应用规范约简，从每个块获得一个目标样本，从而实现正常数速率。 定理5给出了从任意目标分布到BSS/BES的SNIS速率的上界，该上界仅适用于完美安全的SNIS。且该上界对于BSS和BES是紧的，也适用于随机化的完美安全SNIS。 ### 2.3 非线性约简的能力与计算机辅助搜索 随机遗忘线性函数评估（ROLE）源的最大相关性为√1/2。存在使用非线性约简从ROLE到BSS(1/2)的最优速率1/2的SNIS，但使用线性约简的SNIS是常数不安全的。同样，存在使用非线性约简从ROLE到BES(√1/2)的最优速率1的SNIS，而线性约简是常数不安全的。 ### 2.4 2×2源的BSS的SNIS的显式表征 对于目标分布为BSS(ρ′)，源分布(X, Y)的边缘支持大小为2的情况： - 若(X, Y) ≠ BSS(ρ)或(X, Y) = BSS(ρ)但ρ′ ≠ ρk（k ∈ {1, 2, ...}），则从(X, Y)到BSS(ρ′)的任何SNIS是常数不安全的。 - 若(X, Y) = BSS(ρ)，ρ′ = ρk，且BSS(ρ′) ⊑ν f,g BSS(ρ)（