量子科技中心_量科网

已知存在针对复杂性类 𝖭𝖤𝖷𝖯 的多证明人交互式协议（𝖬𝖨𝖯 协议）、针对 𝖭𝖯 的简洁 𝖬𝖨𝖯 协议，以及针对 𝖱𝖤 的共享纠缠多证明人交互式协议（𝖬𝖨𝖯∗ 协议）。多证明人交互式证明系统的这种非凡能力，源于一个假设：在协议过程中，证明人之间不得相互通信。如果允许他们自由通信，则该设置等同于单证明人情形，系统的计算能力将显著减弱。 本文首次研究了允许证明人之间进行通信（即信息泄露）但通信量受限的设置。我们引入了两种技术来处理这一问题，并证明多证明人交互式证明系统能够抵御一定量的信息泄露。第一种技术基于并行重复定理。我们应用该技术表明，对于任意多项式 p，可以分别构造针对 𝖭𝖤𝖷𝖯 和 𝖱𝖤 的双证明人单轮 𝖬𝖨𝖯 和 𝖬𝖨𝖯∗ 协议，这些协议能够抵御 p(n) 比特的泄露。我们进一步推导出第二种技术，将任何低可靠性的 PCP 构造转化为针对 𝖭𝖯 的、能够抵御泄露的双证明人单轮 𝖬𝖨𝖯 协议。我们还讨论了多证明人交互式证明系统中的抗泄露能力与 PCP 文献中的滑动尺度猜想之间的关系。