att_abstract={{In the setting of cryptographic protocols, the corruption of a party
has been viewed as a simple, uniform and atomic operation, where the adversary decides to 
get control over a party and this party immediately gets
corrupted.  In this paper, motivated by the fact that different
players may require different resources to get corrupted, we put forth
the notion of {em resource-based corruptions}, where the adversary
must invest some resources in order to  do so.

If the adversary has full information about the system configuration
then resource-based corruptions would provide no fundamental
difference from the standard corruption model. However, in a
{em resource anonymous} setting, 
in the sense that such configuration is hidden from the
adversary, much is to be gained in terms of efficiency and

We showcase the power of anonymity in the setting of secure multiparty
computation (MPC) with resource-based corruptions and prove that
anonymity can effectively be used to circumvent known impossibility
results. Specifically, if $OPT$ is the corruption budget that violates
the completeness of MPC (the case when half or more of the players are
corrupted), we show that by using anonymity, the completeness of MPC can
be made to hold against an adversary with as much as a $Bcdot OPT$
budget, for any constant $B>1$. This result requires a suitable choice
of parameters (in terms of number of players and their hardness to
corrupt), which we provide and further prove other tight variants of
the result when the said choice is not available. Regarding efficiency
gains, we show that anonymity can be used to force the corruption
threshold to drop from 1/2 to 1/3, in turn allowing the use of much
more efficient (information-theoretic) MPC protocols.

We achieve the above through a series of technical contributions: 

 - the formulation of the notion of {em inversion effort preserving} (IEP) 
functions which is a type of direct-sum property, and the property of 
{em hardness indistinguishability}.
While hardness indistinguishability enables the dissociation of
parties' identities and the resources needed to corrupt them, IEP
enables the discretization of adversarial work into corruption tokens;

 - the modeling of the corruption process in the setting of MPC through 
{em corruption oracles} as well as the introduction of a notion of
reduction to relate such oracles;

 -  the abstraction of the corruption game  as a combinatorial problem 
and its analysis,

all of which may be of independent interest.
	att_authors={dj1576, jg001v},
	att_categories={C_CCF.4, C_CCF.1},
	att_copyright_notice={{(c) ACM, 2012. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 2012 {{, 2013-01-10}}.
	att_tags={multi-party computation, cryptography, buckets and balls},
	author={David Johnson and Juan Garay and Aggelos Kiayias and Moti Yung},
	institution={{ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp 4}},
	title={{Resource-Based Corruptions and the Combinatorics of Hidden Diversity}},