The reseach concerns the computational complexity of feasible computations. The objectives of this project are twofold: to establish a firm complexity theoretic underpinning for public-key cryptography; to reveal the rich structure that individual complexity classes, such as NP, appear to have, and to increase understanding of the structural relations between low-level complexity classes. One emphasis will be to continue research in structural complexity theory that lays a foundation for cryptography. The approach is to base the investigation of existence of cryptographic assumptions (or primitives) directly on structural properties of complexity classes, rather than on presumed intractability of individual concrete problems.
