Cryptographic primitives often define controlled access to (learning and influencing) information, permitting some kind of access while denying others. This parallels the basic questions in computational complexity regarding whether there exist computational tasks that are easy in some sense while being hard in some other sense (e.g. problems in NP\\\\P). As such, it is natural to frame some questions of computational complexity (easiness/hardness combinations) in terms cryptographic primitives. Indeed, Impagliazzo's multiverse, a framework used to discuss various complexity assumptions, consists of two cryptographic worlds (minicrypt and cryptomania), which are related to different cryptographic primitives (private-key encryption and public-key encryption).
In a recent sequence of works, we investigate a possibly broader landscape of complexity assumptions that can be related to a richer collection of cryptographic primitives -- namely, multiparty computation (MPC) primitives. In this talk we shall see the basic ingredients and initial results of this investigation.
First, we shall set up information-theoretic notions of complexity for 2-party computation. This complexity notion is implicitly defined using the partial order of secure reducibility. These information theoretic reductions serve as a baseline for framing computational complexity assumptions of the form that one cryptographic primitive securely reduces to another in a computationally bounded environment. We shall discuss specific results (and some on going research) that throw light on minicrypt and cryptomania, and suggest the possibility of identifying other meaningful intermediate complexity assumptions (this is joint work with Hemanta Maji and Mike Rosulek).
