乘积分布的紧计算不可区分性界限

### 乘积分布的紧计算不可区分性界限 #### 1. 引言 在计算环境中，这些界限可用于弱不经意传输协议的放大，为信息论放大过程在计算上的有效性提供了一种直接的分析方法。在考虑具有多种安全属性的密码学原语时，放大一种属性可能会削弱另一种属性，存在权衡关系。我们期望这些界限能在放大弱化版本的此类原语时，实现更大范围的参数选择。 此外，一个有趣的观察是，电路规模相对于 1/ε 仅呈对数增长，我们将在放大非可忽略问题的背景下进一步探讨这一点。 #### 2. 相关工作 虽然前面提到的耦合技术本身是非构造性的，但 Maurer 和 Tessaro 展示了如何使用 Holenstein 硬核引理的紧版本来推导其计算模拟，这种方法也可用于一般地推导紧界限。然而，我们的直接和特定方法仍有一些优势： - **非均匀设置下的更好参数**：在我们的直接方法中，从区分 D⊗m 和 Q⊗m 的区分器构建 D 和 Q 的区分器时，电路规模大约乘以 log(1/ε)/(1 - d)m。相比之下，使用硬核方法时，电路规模大约乘以 (1/ε)² m² (log |D| + log |Q|)。由于 ε < (1 - d)m 时界限才有意义，所以后者总是更差。 - **简单性和明确性**：硬核引理给出的区分器较为复杂，而我们的区分器相当简单且易于理解。 #### 3. 组织 - 第 2 节介绍基本定义和符号。 - 第 3 节证明非均匀变体及其紧性。 - 第 4 节展示如何将非均匀变体推广到均匀设置。 - 第 5 节演示这些界限的应用。 - 第 6 节提出一个猜想，旨在捕捉与电路规模增长和松弛度相关的异或模拟。 #### 4. 定义 - 对于分布 D，D⊗k 表示 k 个独立副本的分布。 - 对于 Ω 上的分布 X0 和 X1，区分器是一个布尔函数 A : Ω → {0, 1}，我们定义 adv⁺ₐ(X0, X1) := E [A(X1) - A(X0)]（如果 A 不是确定性的，期望也对 A 取）。如果对于任何规模为 s 的电路 C，都有 adv⁺ₐ(X0, X1) ≤ d，则称分布 X0 和 X1 对于规模为 s 的电路是 d 不可区分的。 - 对于分布 X 和 Y，(X, Y) 表示乘积分布，由 X 和 Y 的两个独立样本组成。 - B(p) 表示参数为 p 的伯努利分布，Bₗ(p) 表示以概率 p 等于 1ₗ，否则等于 0ₗ 的分布。 - 对于字符串 s，s[i] 表示 s 的第 i 位。 - [m] 表示集合 {1, ..., m}。 - X₁/₂ 表示由 b ← {0, 1}，x ← Xb 给出的分布。 - 分布族 X = {Xₙ} 是有效可采样的，如果存在一个均匀的概率多项式时间（PPT）采样器，给定 1ₙ 输出 Xₙ 的一个样本。 #### 5. 符号说明 当同一分布在单个表达式中多次使用时，例如 (f(D), g(D)) 中的 D，应解释为采样一个单一值 d ← D 并同时提供给 f 和 g，而不是两个独立样本。 #### 6. 非均匀界限及其紧性 ##### 6.1 非均匀版本 我们从非均匀版本开始，因为它更简单清晰，均匀版本是下面思想的推广。大致来说，给定 (X0, Y0) 和 (X1, Y1) 的区分器 C，如果对于所有的 x 值，C(x, ·) 不是 Y0 和 Y1 的足够好的区分器，那么我们可以构建 X0 和 X1 区分器的放大器。然后使用这个放大器将总是输出 1 的平凡区分器转换为足够好的区分器。 **定理 2**：设 X0 和 X1 是 ℓₓ 位上的分布，对于规模为 sₓ 的电路是 dₓ 不可区分的（Y0 和 Y1 分别对应 ℓᵧ、dᵧ、sᵧ）。那么，对于每个 k ∈ N，(X0, Y0) 和 (X1, Y1) 对于规模为 sₖ 的电路是 (dₓ + dᵧ - dₓ · dᵧ + εₖ) 不可区分的，其中 εₖ := (dᵧ)ᵏ · dₓ (1 - dᵧ) / (1 - (dᵧ)ᵏ) ≤ (dᵧ)ᵏ sₖ := min {sᵧ - ℓₓ, (sₓ - 1) / k - 5ℓᵧ - 1} **证明思路**：假设存在规模为 sₖ 的电路 C，使得 adv⁺ₐ((X0, Y0), (X1, Y1)) > (dₓ + dᵧ - dₓ · dᵧ + εₖ)。对于每个固定的 x，C(x, ·) 区分 Y0 和 Y1 的优势至多为 dᵧ。通过一系列推导，我们可以构建一个新的区分器 A′ 用于区分