Worst-Case v.s. Average-Case Complexity and Applications to Secure Cryptography
Jin-Yi Cai Principal Investigator
MetadataShow full item record
CCR-98-20806 <br/><br/>PI: Cai, Jin-Yi <br/><br/>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.