Cryptography with Work-based Corruptions and the Combinatorics of Anonymity
Seminar Room 1, Newton Institute
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 talk, motivated by the fact that different players may require different resources to get corrupted, we introduce the notion of resource-based corruptions, where the adversary must invest some resources in order to perform corruptions. 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 the `anonymous' setting (where anonymity is 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 anonymity in the setting of secure multiparty computation with resource-based corruptions and prove that anonymity can effectively be used to circumvent impossibility results. 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 more efficient cryptographic protocols in various settings. Joint work with Juan Garay, David Johnson (AT&T), Moti Yung (Google).