Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question.
We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ... more >>>

We develop new tools to study the relative complexities of secure
multi-party computation tasks (functionalities) in the Universal
Composition framework. When one task can be securely realized using
another task as a black-box, we interpret this as a
qualitative, complexity-theoretic reduction between the two tasks.
Virtually all previous characterizations of ... more >>>