公共币与私有币协议

形式陈述

公共币协议在看到输入前抽取随机串 $R$ ，Alice 与 Bob 都能读取它。给定 $R=r$ 后，协议成为一棵确定性通信树。公共随机串独立于 $(x,y)$ ，不计入消息长度；它协调双方选择同一个哈希函数、采样位置或协议分支，却不能携带当前输入的信息。

私有币协议则让 Alice 持有 $R_A$ 、Bob 持有 $R_B$ ，两条随机带彼此独立并对另一方隐藏。任何想让双方共同使用的随机选择都必须通过实际消息协调。私有币不是“双方共享猜测”：Alice 不知道 $R_B$ ，Bob 也不知道 $R_A$ 。

记逐输入错误至多 $\varepsilon$ 、最坏通信硬上限下的复杂度为

R^{\mathrm{pub}}_\varepsilon(f), \qquad R^{\mathrm{priv}}_\varepsilon(f).

私有币协议可以忽略各自随机带，公共币协议也可以把一方生成的随机性视为自己的公共选择，因此在标准模型中

R^{\mathrm{pub}}_\varepsilon(f) \le R^{\mathrm{priv}}_\varepsilon(f).

这条不等式只比较通信，不表示公共随机性在实现中没有生成或同步成本。

设双方输入总长度至多 $N$ bit，一条公共币协议通信至多 $c$ ，且每个输入错误至多 $\varepsilon$ 。对额外参数 $\delta>0$ ，Newman 思想给出

R^{\mathrm{priv}}_{\varepsilon+\delta}(f) \le R^{\mathrm{pub}}_\varepsilon(f) +O\!\left(\log N+\log\frac1\delta\right).

结论允许错误从 $\varepsilon$ 增至 $\varepsilon+\delta$ 。它不是说公共币和私有币逐协议完全等价，而是在有限输入全集、允许小误差松弛时，公共随机性只节省对数级通信。

对每个固定输入 $u=(x,y)$ ，令 $E_u(r)\in\{0,1\}$ 表示公共串 $r$ 是否导致错误，且 $\mathbb E_R E_u(R)\le\varepsilon$ 。独立抽取 $t$ 条公共串 $R_1,\ldots,R_t$ 。Hoeffding 界说明

\Pr\!\left[ \frac1t\sum_{j=1}^tE_u(R_j)>\varepsilon+\delta \right] \le e^{-2t\delta^2}.

合法输入对至多 $2^N$ 个。取 $t=O(N/\delta^2)$ ，对全部输入求并后失败概率小于 $1$ ；因此存在一个固定多重集 $\{r_1,\ldots,r_t\}$ ，使每个输入在其中至多 $\varepsilon+\delta$ 比例的随机串上出错。

把这个多重集公开写入协议。Alice 用私有币均匀选择 $J\in[t]$ ，发送 $J$ 的编号；双方随后按原公共币协议使用固定串 $r_J$ 。编号长度

\lceil\log_2t\rceil =O\!\left(\log N+\log\frac1\delta\right),

且每个输入的错误率由构造控制在 $\varepsilon+\delta$ 。这完成从公共币到私有币的模拟；新消息不是“免费公共随机串”，而是把小随机样本族中的索引实际传给 Bob。

直觉

公共币提供的是协调，不是输入带宽。双方免费看到同一随机选择，因而可以不通信就对齐哈希函数或采样位置；私有币只在各自一侧存在，任何共同选择都必须通过消息建立。两种模型的差距来自同步随机决策的成本。

Newman 压缩说明有限输入空间并不需要保留无限大的随机宇宙。只要抽出一个对每个输入都保持近似错误率的小样本族，协议就只需传送族内索引。并集界负责同时覆盖所有输入，增加的 $\delta$ 则为有限抽样留下余量。

例子与边界

在Equality内积指纹中，公共随机向量 $r$ 使双方计算同一个 parity。Alice 只发送指纹 bit，Bob 比较自己的指纹； $k$ 次独立公共选择把错误降为 $2^{-k}$ 。

若 Alice 用私有币抽 $r$ ，Bob 无法仅从一个 parity bit 知道她采用哪个线性函数。发送整个 $n$ -bit 向量会抹掉通信优势；发送一个来自预先约定小族的种子则可能保留优势，但种子长度必须进入通信。区别不在哈希公式，而在双方如何获得同一个随机函数。

固定一个公共随机串并永久写入协议，也不能给出逐输入正确的短确定性方案。对每个固定压缩映射总有碰撞输入；公共币保证的是每个固定输入只在少量随机串上碰撞，而不是存在一条随机串同时避开所有输入。

证明对有限输入全集求并，因而输入长度界 $N$ 必须明确。若输入来自无限精度实数、协议族没有有限离散化，不能把 $2^N$ 的计数凭空代入。通信上限、错误量词和随机串独立性也都要固定。

$R$ 若在看到输入后由某个中央实体选择，就可能把输入编码进“公共随机性”，那已是额外通信或建议字符串。伪随机种子在工程上能否替代真公共币，则依赖对手能力和生成器假设，不是信息论模型自动保证。

随机性压缩控制平均于所选小族的错误，不保证每条 $r_j$ 都对所有输入正确。模拟后仍是随机协议；把 Alice 发送的索引固定为某个常数，会再次落入确定性碰撞障碍。

推论与应用

公共币协议总可视为确定性协议树的输入无关分布，私有币协议则需要把各自不可见的随机选择纳入本地 view。固定随机性做下界时，必须固定一条对所选输入分布平均表现良好的随机带，而不能为每个输入挑不同的最佳带。

在有限输入、允许小幅增加错误的标准通信模型里，Newman 定理让 public-coin 与 private-coin 复杂度至多相差对数级附加通信。这个结论为模型转换提供上界，却不免除协议逐项报告输入长度、错误松弛、硬通信上限和共享随机性来源。

参考资料

Ilan Newman, “Private vs. Common Random Bits in Communication Complexity,” Information Processing Letters 39(2), 1991, pp. 67–71.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Section 3.4.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 3.