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.
