Verifiably Secure Devices
We put forward the notion of a verifiably secure device, in essence a stronger notion of secure computation, and achieve it in the ballot-box model. Verifiably secure devices
- PDF / 683,140 Bytes
- 29 Pages / 430 x 660 pts Page_size
- 53 Downloads / 181 Views
MIT Department of Economics [email protected] 2 BBN Technologies [email protected] 3 MIT CSAIL [email protected]
Abstract. We put forward the notion of a verifiably secure device, in essence a stronger notion of secure computation, and achieve it in the ballot-box model. Verifiably secure devices 1. Provide a perfect solution to the problem of achieving correlated equilibrium, an important and extensively investigated problem at the intersection of game theory, cryptography and efficient algorithms; and 2. Enable the secure evaluation of multiple interdependent functions.
1
Introduction
From GMW to ILM1 Security. As put forward by Goldreich, Micali and Wigderson [11] (improving on two-party results of Yao [17]), secure computation consists of capturing crucial aspects of an abstract computation aided by a trusted party, by means of a concrete implementation that does not trust anyone. However, what is deemed crucial to capture and what constitutes an implementation have been changing over time. In order to achieve fundamental desiderata in a game theoretic setting, where incentives are added to the mixture and players are assumed to behave rationally, in [13] we put forward a stronger notion of secure computation, and achieved it in the ballot-box model. In essence, this is a physical model using ballots and a ballot randomizer, that is, the same “hardware” utilized from time immemorial for running a lottery and tallying secret votes. We refer to our 2005 notion as ILM1 security. Our main reason for introducing ILM1 security was implementing normal-form mechanisms in the stand-alone setting. ILM2 Security. In this paper, we put forward a yet stronger notion of secure computation, herein referred to as ILM2 security, and achieve it in a variant of the ballot-box model. ILM2 security enables us to attain even more sophisticated applications. In particular, it enables us to (1) perfectly achieve correlated equilibrium, a crucial desideratum at the intersection of cryptography, game theory, and efficient algorithms; and (2) securely implement interdependent functions and mechanisms. R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 273–301, 2008. c International Association for Cryptologic Research 2008
274
S. Izmalkov, M. Lepinski, and S. Micali
Setting Up A Comparison. In an fairer world, we could have come up with our present security notion in 2005. But the world is not fair, and we could not even conceive ILM2’s security requirements back then. To ease their comparison, we sketch both approaches in the next two subsections, initially focussing on the secure evaluation of a single, probabilistic, finite function f from n inputs to n + 1 outputs. Without loss of generality, f : ({0, 1}a)n → ({0, 1}b )n+1 . We break each approach into the following components: (1) The Ideal Evaluation, describing the “target computation”, that is, an evaluation of f with the help of a trusted party; (2) The Concrete Model, highlighting the “mechanics” of an evaluation of f without a trusted party; and (3) The Security Notion, describing
Data Loading...
