#quantum-zero-knowledge

共收录 1 条相关安全情报。

← 返回所有主题
推荐 8.5
Conf: 50%
👥 作者: Zihan Hu, Yupan Liu

本文研究带简洁证明者(laconic prover)的两消息量子交互证明系统,即证明者单次回复长度被严格限制为 ℓ 比特时的可验证问题类。经典情形由 Goldreich、Vadhan 与 Wigderson(CC 2002)引入,刻画了证明者通信量为对数级的多项式时间可验证问题;量子情形中,Watrous(FOCS 2002)已证明即便证明者只回复一个比特,该类也包含量子统计零知识 QSZK,而 Beigi、Shor 与 Watrous(ToC 2011)指出,一旦把验证者的问题限制为经典公开硬币,对应类便坍缩到 BQP。本文形式化定义类 QIP_{ℓ-bit}(2),并给出三项结果:其一,用多状态可区分性(Multi-State Distinguishability)对该类作完全刻画,由此证明量子态可区分性 QSD 是 QIP_bit-完全问题;又因 QSD 为 QSZK-难,说明 ℓ≥2 时 QIP_{ℓ-bit}(2) 处于“略高于” QSZK 的复杂度位置。其二,给出坍缩到 QSZK 的“容易区间”:当 a(n)−b(n) ≥ 1/O(log n) 时,QSD[a,b](从而 QIP_bit[a,b])落入 QSZK;并通过把 QIP_{ℓ-bit}[2,c,s] 的答案压缩到 QIP_bit,得到另一条件 2c > (1+2^{ℓ/2})s。其改进的极化(polarization)技术同时适用于 SD 与 SZK,解决了 Sahai 与 Vadhan(JACM 2003)遗留的公开问题。其三,证明量子公开硬币同样使交互失去作用:常数间隙下 qc-QAM[O(√log n)] ⊆ BQP,其中 qc-QAM[ℓ] 是 QIP_{ℓ-bit}(2) 的子类,验证者的问题恰为 EPR 对的一半。该工作属量子计算复杂性理论研究,适合量子密码、零知识证明与复杂性理论方向的研究者阅读。

💡 推荐理由: 界定了量子零知识类在证明者回复极短时的能力边界,说明量子公开硬币与经典公开硬币都会导致复杂度类坍缩;对后量子零知识协议与量子认证协议的假设选择有理论指导意义,并推进了经典 SZK 极化这一长期公开问题。

🎯 建议动作: 研究跟进:纳入内部密码学与量子安全理论跟踪清单,评估其对现有量子零知识协议假设的影响

排序因子: 影响边界/网络设备 (+5) | 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)