We aim to base a variety of cryptographic primitives on complexity theoretic assumptions. We focus on the assumption that there exist highly structured problems --- admitting so called "zero-knowledge" protocols --- that are nevertheless hard to compute

Most of modern cryptography is based on the conjectured hardness of some very specific problems like factoring.A prominent goal in cryptographic research is to base cryptography on a firmer complexity theoretic footing, such as the assumption that P is not equal to NP (which we know is necessary). This seems very far from our current understanding and so we aim to base cryptographic primitives on general complexity theoretic assumptions, albeit ones that are stronger than P not equals NP. Specifically, the assumption that P is not equal to NP means that there exists a language L that (1) is not in P but (2) is in NP. In this project we consider strengthening this assumption in two ways: 1) We assume that L is hard to compute for most instances (rather than merely hard in the worst-case). 2) We assume not only that L belongs to NP, but that it has additional structure. In particular, we assume that L is in the complexity class SZK, that is, membership in L can be proved by "statistical" zero-knowledge proofs -- interactive proofs that reveal nothing but the validity of the statement. So far, we have proved that this assumption yields public-key encryption schemes, as long as we further assume that the zero-knowledge protocol also satisfies certain natural structural properties. We have also shown that a variant of the above assumption yields a certain generalization of "collision resistant hash functions" - hash functions that are compressing but for which it is computationally difficult to find collisions.