Worst-Case v.s. Average-Case Complexity and Applications to Secure Cryptography

Ccr-98-20806 PI：蔡金义本项目研究最坏情况和平均情况复杂性理论之间的内在联系，以及理解这些联系在基于最坏情况困难假设的安全公钥密码系统设计中的应用。这个项目的目标是在广义上研究这种最坏情况/平均情况的联系，完善目前证明的仅基于最坏情况复杂性假设的密码系统的结果，并开发仅基于最坏情况复杂性假设的实用、安全的公钥密码系统。所提出的工作还将促进平均案例复杂性的一般理论的发展。

CCR-98-20806 PI: Cai, Jin-Yi This project is a study of the inherent connections between worst case and average case complexity theory and applications of understanding these connections to the design of secure public-key cryptosystems based on assumptions of hardness in the worst case. The goals of this project are to investigate this worst case / avaerage case connection in a broad sense, to refine the currently proven results that base a cryptosystem only on worst case complexity assumptions, and to develop practical, secure public-key cryptosystems that are based only on worst case complexity assumptions. The proposed work will also advance the general theory of average case complexity.