匿名传输协议的研究与分析

### 匿名传输协议的研究与分析 #### 1. 研究成果与开放问题 在相关研究中，对细粒度匿名传输（AT）进行了扩展，使其能够直接传输 ℓ 位消息，且安全性与单比特 AT 相同，但所需轮数翻倍。同时，在指定发送者环境下，以非平凡（但不太实用）的 ε 和 δ 参数实例化了渐近安全的 AT。此外，定义了一种名为强 AT 的 AT 扩展，这是不可检测计算所必需的，还定义了不可检测版本的不经意传输（UOT）和多方计算（UMPC），其中 k 方在 N 个人的群体中隐藏各自的执行过程。基于强 AT 实现了 UOT，并用于 k = 3 时的 UMPC 实例化。 研究还留下了两个有趣的问题： 1. 对于具有压倒性正确性和匿名性的渐近安全 AT 的不可能结果，能否扩展到排除匿名性为 1 - 1/poly(κ) 的渐近安全 AT？ 2. 是否可以在细粒度环境下，基于“Obfustopia”标准假设实现与现有实例化参数相似的 AT？ 若这两个问题都能得到肯定回答，将区分渐近安全领域和细粒度安全领域。 #### 2. 预备知识 ##### 2.1 符号表示 - 对于任何一方 P，用 TP 表示其随机磁带。 - 对于事件 (A, B)，¯A 表示 A 的互补事件，Pr[A | B] 表示在 B 发生的条件下 A 发生的概率。 - 对于值 (a, b)，符号 a = b 表示相应谓词的位值。 - 用 κ 表示安全参数，negl(κ) 表示关于 κ 可忽略的任何函数，owhl(κ) 表示关于 κ 压倒性的函数（即 1 - owhl(κ) = negl(κ)）。 - 对于任何概率分布 D，用 R(D) 表示 D 的支撑集，x $← D 表示 x 从 D 中均匀采样。 - 对于概率分布 p 和 q，p⊗t 表示从 p 中取 t 个样本得到的分布，p ◦ q 表示从 p 中采样一次，从 q 中采样一次得到的分布，∥p∥1 表示 p 的 L1 范数。 - 对于两个位串 A, B ∈ {0, 1}m，A ⊕ B 表示 A 和 B 的按位异或。 - 用 [n] 表示 n ∈ N 的数字集合 {1, ..., n}。 ##### 2.2 分布测试 首先介绍两个分布之间的总变差距离： - **定义 1（总变差距离）**：设 p 和 q 是可数集可能结果 Ω 上的两个概率分布，p 和 q 之间的总变差距离定义为： \[d_{TV}(p, q) := \frac{1}{2} \sum_{\omega \in \Omega} |p(\omega) - q(\omega)| = \frac{1}{2} \|p - q\|_1\] 总变差距离的一个重要性质是，在进行多次采样时它具有次线性性质。当从伯努利分布中取 t 个样本时，相应的分布可以通过从 t 位二项分布中取单个样本描述。次可加性限制了相应二项分布的总变差距离： - **引理 1（t 倍概率分布的总变差距离）**：设 p 和 q 是两个总变差距离为 dTV(p, q) 的伯努利分布，那么对于从各自分布中采样 t 次得到的二项分布 p⊗t 和 q⊗t，有： \[d_{TV}(p^{\otimes t}, q^{\otimes t}) \leq t \cdot d_{TV}(p, q)\] 对于两个不同的分布，区分器需要区分两个样本是来自 p⊗r 还是 q⊗s 时，有如下规则： - **引理 2（乘积分布总变差距离的次可加性）**：设 p 和 q 是 {0, 1}m 上总变差距离为 dTV(p, q) 的概率分布，r 和 s 是总变差距离为 dTV(r, s) 的两个伯努利分布，那么对于从每个分布中采样一次并连接输出得到的分布（即来自 {0, 1}m + 1，可能来自 p ◦ r 或 q ◦ s），有： \[d_{TV}(p \circ r, q \circ s) \leq d_{TV}(p, q) + d_{TV}(r, s)\] 以下引理限制了基于单个样本区分两个分布 p 和 q 的区分器的区分优势： - **引理 3（基于总变差距离区分分布）**：设 p 和 q 是总变差距离为 dTV(p, q) 的两个分布，如果 dTV(p, q) < 1/3，那么不存在基于单个样本以概率 ≥ 2/3 区分 p 和 q 的算法。 利用引理 1 和 3，可以给出以优势 α/2 区分两个分布 p 和 q 的采样复杂度的下界： - **推论 1（用 t 个样本区分两个伯努利分布）**：任何以概率 ≥ 1/2 + α/2 区分 p 和 q 的区分器 D 需要 t ∈ Ω(α / dTV(p, q)) 个样本。 #### 3. 匿名传输 考虑这样一种情况：某个秘密特工 Pb 希望将消息 Σ 传输给接收者 R，同时在两个人中隐藏其身份 b。将实现这一目标的交互式协议称为匿名传输（AT）。 ##### 3.1 网络模型和非参与方 匿名传输协议的目标是将传输的消息隐藏在不参与协议的个人的正常对话中。根据隐写术中的一个成熟结果，这个任务可以简化为将传输的消息隐藏在其他个人广播的均匀随机信标中，即均匀信道，其中所有协议消息看起来都是均匀随机的，并且可以编译成任何其他普通通信模式。因此，考虑一组 k 方通过广播信道相互交互，并专注于均匀信道的协议，将非参与方建模为“虚拟方”，它们在每一轮只广播固定长度的均匀随机消息。 ##### 3.2 模型 设 b ∈ {1, ..., N - 1} 表示发送者的索引，Σ ∈ {0, 1}ℓ 是 Pb 要传输给接收者的消息。考虑在公共参考字符串（CRS）模型下 N 个玩家（P1, ..., PN - 1, R）之间的交互式协议，其中 R 和 Pb 参与协议，而 i ≠ b 的 Pi 是非参与但存在的玩家，仅广播随机字符串。接收者 R 将 CRS 作为输入，发送者 Pb 将 CRS 和消息 Σ 作为输入。对于任何玩家 P，用 TP 表示其随机磁带。玩家通过同步模型中的认证广播信道进行交互，协议按轮进行，每个玩家在每一轮广播一条消息。用 ⟨R, P1, ..., PN - 1⟩(crs, b, Σ) 表示在这种设置下协议可能的转录本分布，概率是在玩家 P ∈ {R, P1, ..., PN - 1} 的随机磁带 TP 和 CRS crs 的随机选择上取的。 - **定义 2（(ε, δ, c, ℓ)-匿名传输）**：对于 ε, δ ∈ R[0, 1] 和 N, c, ℓ ∈ N（所有可能是 κ 的函数）的 N 方 (ε, δ, c, ℓ)-匿名传输（AT）是一个包含三个 PPT 算法（Setup, Transfer, Reconstru