量子零知识交互式证明（论证）系统：复杂性和安全性

Zero-knowledge interactive proof/argument system lies in the boundary between the study of complexity theory and cryptography. On one hand, it induces interesting complexity classes such as IP and ZK, which play an important role in complexity theory. On the other hand, its security against verifier (known as soundness), and against prover (known as zero-knowledge), are of great importance in cryptography. As quantum technology is more and more mature, we are now becoming interested in generalizing many notions related to zero-knowledge interactive proof/argument system to the quantum setting, where both quantum computation and quantum communication are allowed. It turns out that we encounter new obstacles in studying quantum zero-knowledge interactive proof/argument system compared with its classical counterpart, e.g., new difficulties in hardness amplification and rewinding, as pointed out in the proposed project. This forces us to develop new (mathematical or complexity-theoretic) tools and techniques that are applicable in the quantum setting. While our study is theoretical, it will nevertheless be helpful and instructive for future realization of cryptographic systems that are secure against quantum attack. Thus, our project is both of scientific value and practical importance.

零知识交互证明（或论证）系统属于复杂性理论和密码学研究的交界。一方面，由它引入了一些有趣的复杂性类，像IP和ZK，都在复杂性理论中扮演着重要角色。另一方面，它针对verifier的安全性（称为可靠性），以及针对prover的安全性（称为零知识），都在密码学中起着重要作用。随着量子技术的日趋成熟，我们现在希望把许多零知识交互证明（或论证）系统的概念推广到量子情形---此时我们允许量子计算和量子通信。研究表明，在研究量子零知识交互证明（或论证）系统的过程中，我们遇到了经典情形中没有的困难。例如，申请书中提到的困难性放大和回绕技术遇到的新困难。这迫使我们发展适用于量子情形的新的（数学或计算复杂性理论）工具和技术。尽管我们的研究是纯理论的，它无疑将对今后实现抵抗量子攻击的密码系统起着有益的指导作用。因此，本项目研究既富有科学价值、又具有实践意义。

零知识交互证明（或论证）系统属于复杂性理论和密码学研究的交界。其针对验证者的安全性（称为可靠性），以及针对证明者的安全性（称为零知识），都在密码学中起着重要作用。随着量子技术的日趋成熟，我们现在希望把零知识交互证明（或论证）系统的概念推广到量子情形---此时我们允许量子计算和量子通信。..在这个项目中，我们研究量子零知识证明/论证系统，以及其构造中重要的一个部件---量子比特承诺。我们还推广我们的安全性证明技术到关于量子比特承诺新的应用。特别地，我们取得了如下研究结果：..1. 基于统计绑定的量子比特承诺方案，我们为所有NP语言构造量子零知识证明系统。..2. 基于计算绑定的量子比特承诺方案，我们为所有NP语言构造量子零知识论证系统。..3. 基于统计绑定的量子比特承诺方案，我们为所有NP语言构造量子零知识知识的证明。..4. 我们发现了量子比特承诺方案一些及其引入注明的性质，例如非交互性，严格绑定性，以及低复杂性假设，等等。..5. 我们研究一般量子比特承诺方案的并行合成性质。对于统计绑定的量子比特承诺方案，我们证明了并行合成得到的量子字符串承诺方案满足最强的“和绑定”性。对于统计绑定的量子比特承诺方案，我们证明了并行合成得到的量子字符串承诺方案满足的“谓词绑定”性。研究表明，谓词绑定性极不平凡，并且在NP语言的量子零知识论证系统的合理性安全分析中，扮演着非常重要的作用。..6. 我们证明了当使用统计量子比特承诺方案时，著名的量子健忘传输协议的安全性。..我们的研究结果兼具理论和实践上的重要意义。首先，尽管我们的构造都是模仿一些著名的经典协议，但使用的却是量子（而非经典）比特承诺方案。因此，我们的构造是全新的。不仅如此，我们的构造能够达到更低的论述复杂性，却依赖于更弱的量子复杂性假设。这使得我们的构造在将来有应用于实践的潜力。第二，我们的安全性分析是全新的。为了我们的目的，我们发展了一些全新的技术，包括“扰动法”和“假设测量法”。我们还引入并且分别证明了并行合成量子比特承诺方案的和绑定性和谓词绑定性。我们相信我们的技术以及概念会在未来的量子密码学研究中找到更多的应用。