Resource-based Corruptions and the Combinatorics of Hidden Diversity: Aggelos Kiayias, U. of Athens & UCONN

Starts:
10:00 am on Monday, November 26, 2012
Ends:
12:00 pm on Monday, November 26, 2012
Location:
MCS 137
Abstract. In the setting of cryptographic protocols, the corruption of a party has traditionally 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 resource-based corruptions, where the adversary must invest some resources in order to corrupt them. 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 resource “anonymous” setting, in the sense that such configuration is hidden from the adversary, much is to be gained in terms of efficiency and security. We showcase the power of such hidden diversity in the context of secure multiparty computation (MPC) with resource-based corruptions and prove that it 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 if hidden diversity is available, the completeness of MPC can be made to hold against an adversary with as much as a B · 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 hidden diversity 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. Among others, the talk will go into details regarding the modeling of the corruption process, the abstraction of the corruption game as a combinatorial problem, and the formalization of the properties of inversion effort preserving functions and hardness indistinguishability that are needed to model hidden diversity in the setting of computational corruptions. Joint work with Juan Garay, David Johnson, Moti Yung.