Claudio Orlandi

On the Necessary and Sufficient Assumptions for UC Computation

Ivan Damgård and Jesper Buus Nielsen and Claudio Orlandi

We study the necessary and sufficient assumptions for universally
composable (UC) computation, both in terms of setup and computational
assumptions. We look at the common reference string model, the common
random string model and the public-key infrastructure (PKI) model, and
provide new result for all of them. Perhaps most interestingly we show that:

- For even the minimal meaningful PKI, where we only assume that the
secret key is a value which is hard to compute from the public key, one
can UC securely compute any poly-time functionality if there exists a
passive secure oblivious-transfer protocol for the stand-alone model.
Since a PKI where the secret keys can be computed from the public keys
is useless, and some setup assumption is needed for UC secure
computation, this establishes the best we could hope for the PKI model:
any non-trivial PKI is sufficient for UC computation.

- We show that in the PKI model one-way functions are sufficient for UC
commitment and UC zero-knowledge. These are the first examples of UC
secure protocols for non-trivial tasks which do not assume the existence
of public-key primitives. In particular, the protocols show that
non-trivial UC computation is possible in Minicrypt.