On the Necessary and Sufficient Assumptions for UC Computation
Speaker: Claudio Orlandi , University of Aarhus
Date: September 25 2009
Time: 10:30AM to 12:00PM
Location: 1st flr conf. ctr, Microsoft Research NE
Contact: Be, 3-6098, imbe@mit.edu
Relevant URL:
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.
This is joint work with Ivan Damgaard and Jesper Nielsen.
See other events that are part of CIS/Microsoft Seminars 2009/2010
See other events happening in September 2009
