In collusion-free protocols, subliminal communication is impossible and parties are thus unable to communicate “any information beyond what the protocol allows”. Collusion-free protocols are interesting for several reasons, but have specifically attracted attention because they can be used to reduce trust in game-theoretic mechanisms. Collusion-free protocols are impossible to achieve (in general) when all parties are connected by point-to-point channels, but exist under certain physical assumptions (Lepinksi et al., STOC 2005) or in specific network topologies (Alwen et al., Crypto 2008).
This work provides a “clean-slate” definition of the stronger notion of collusion preservation. The goals in revisiting the definition are:
· To give a definition with respect to arbitrary communication resources (that includes as special cases the communication models from prior work). We can then, in particular, better understand what types of resources enable collusion-preserving protocols.
· To construct protocols that allow no additional subliminal communication in the case when parties can communicate (a bounded amount of information) via other means. (This property is not implied by collusion-freeness.)
· To provide a definition supporting composition, so that protocols can be designed in a modular fashion using sub-protocols run among subsets of the parties.
In addition to proposing the definition, we explore necessary properties of the underlying communication resource. Next we provide a general feasibility result for collusion-preserving computation of arbitrary functionalities. We show that the resulting protocols enjoy an elegant (and surprisingly strong) fallback security even in the case when the underlying communication resource acts in a Byzantine manner. Finally, we investigate the implications of these results in the context of mechanism design.
|Commitee:||Gennaro, Rosario, Malkin, Tal, Shoup, Victor, Subramanian, Lakshmi|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 73/03, Dissertation Abstracts International|
|Keywords:||Collusion free, Collusion preservation, Collusion-free protocols, Cryptography, Mechanism design, Multiparty computation|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be