通讯、密码及量子信息之复杂性问题研究

在过去的30年里，计算复杂性已经成为信息科学最为主要的研究领域之一。计算复杂性的研究不仅仅局限于具体问题的优化算法设计，更为重要的是，这种研究旨在搭建理论框架，促使新型应用成为可能。在本项目中，我们准备从三个层次探索复杂性问题。首先，本项目着眼于研究量子计算复杂性，目的在于理解这项新型技术的功耗与限制。我们尤其希望研究量子多证明者验证系统下能够实现的计算可靠性问题。其次，本项目准备研究密码学中的复杂性问题，尤其希望研究最近提出的非交换群中图形基础下安全多方计算效率问题，并研究互联网环境下基于复杂性的密码学理论。第三，本项目意在研究通信复杂性中的下限问题。例如，我们希望检测通信复杂性同类功能下的某些对称属性。这些题材的研究需要各种不同的数学技术，我们预期将会运用并发展离散数学，拓扑学、几何、代数等方面的数学工具。

计算复杂性是信息科学重要研究领域之一，其研究不仅限于具体问题的优化算法设计，更重要的是搭建理论框架，促使新型应用成为可能。互联网的普及以及量子信息的前景，均为此类新型应用提供了绝佳表现机会。本项目从三个层面探索复杂性问题。第一在基础层面上，研究计算及通信复杂中的上限及下限问题，对此领域中核心观念，如设计伪随机生成器进行探索。第二在应用层面上，研究密码学中的复杂性问题，对已有密码技术进行安全分析，并对如何优化设计进行探索。第三在前瞻性层面上，研究量子信息及复杂性，深入了解这项新型信息技术的基础及应用。以清华大学交叉信息研究院为基地，本项目进展顺利。在以上三个不同方向研究计算复杂性，取得了良好的研究及人才培养成果。这些方向彼此密切关联，他们的研究相辅相成。例如，密码学及量子通信学是建筑在计算复杂性的数学基础上，伪随机数生成在密码学及计算复杂性两个领域中都是中心问题，量子博弈论是量子信息和密码学的交叉领域等等。在量子博弈上，成果同时包括了理论推导及物理实验论证，这是本项目的另一成功特色。在四年里，本项目完成200余篇国际会议/期刊论文，包括12篇在理论计算机顶级会议STOC，FOCS，SODA，CCC上发表，以及10篇在密码学顶级会议CRYTO，Eurocrypt上发表。培养了11位博士生毕业。