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

最坏情况与最差情况

• 批准号: 9820806
• 负责人: Jin-Yi Cai
• 金额: $ 22万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-01 至 2001-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9820806&HistoricalAwards=false
• 关键词: Worst; Case; v.s.; Average; Complexity

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.

CCR-98-20806 PI：Cai，Jin-Yi本项目研究最坏情况和平均情况复杂性理论之间的内在联系，以及理解这些联系在基于最坏情况下的硬度假设的安全公钥密码系统设计中的应用。 这个项目的目标是调查这种最坏情况/平均情况下连接在广义上，完善目前证明的结果，基于密码系统的最坏情况下的复杂性假设，并开发实用，安全的公钥密码系统，仅基于最坏情况下的复杂性假设。 本文的工作也将推进平均案例复杂度的一般理论。