New Impossibility Results
for Concurrent Composition and a Non-Interactive Completeness Theorem for
Secure Computation
Shweta Agrawal (UCLA)
Vipul Goyal (MSR,
Abhishek Jain
(UCLA)
Manoj Prabhakaran (UIUC)
Amit Sahai (UCLA)
Abstract:
We consider the client-server setting for the concurrent composition of
secure protocols: in this setting, a single server interacts with multiple
clients concurrently, executing with each client a specified protocol where
only the client should receive any nontrivial output. Such a setting is
easily motivated from an application standpoint. There are important special
cases for which positive results are known such as concurrent zero knowledge
protocols and it has been an open question whether other natural
functionalities such as Oblivious Transfer (OT) are possible in this setting.
In this work:
- We resolve this open question by showing that unfortunately, even in this
very limited concurrency setting, broad new impossibility results hold,
ruling out not only OT, but in fact all nontrivial finite asymmetric
functionalities. Our new negative results hold even if the inputs of all
honest parties are fixed in advance, and the adversary receives no auxiliary
information.
- Along the way, we establish a
new unconditional completeness result for asymmetric functionalities, where
we characterize functionalities that are non-interactively complete
secure against active adversaries. When we say that a functionality F is
non-interactively complete, we mean that every other asymmetric functionality
can be realized by parallel invocations of several copies of F, with no other
communication in any direction. Our result subsumes a completeness result of Kilian [STOC'00] that uses protocols which require
additional interaction in both directions.