On Fairness in Secure Computation
| dc.contributor.advisor | Katz, Jonathan | en_US |
| dc.contributor.author | Gordon, Samuel Dov | en_US |
| dc.contributor.department | Computer Science | en_US |
| dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
| dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
| dc.date.accessioned | 2011-02-19T06:41:46Z | |
| dc.date.available | 2011-02-19T06:41:46Z | |
| dc.date.issued | 2010 | en_US |
| dc.description.abstract | Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980's demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the <italic>fairness</italic> property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of <italic>partial</italic> fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of <italic>rational</italic> adversaries, and, finally, we further study the difficulty of achieving fairness by exploring how much external help is necessary for enabling fair secure computation. | en_US |
| dc.identifier.uri | http://hdl.handle.net/1903/11117 | |
| dc.subject.pqcontrolled | Computer Science | en_US |
| dc.subject.pquncontrolled | cryptography | en_US |
| dc.subject.pquncontrolled | fairness | en_US |
| dc.subject.pquncontrolled | secure computation | en_US |
| dc.title | On Fairness in Secure Computation | en_US |
| dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1