On time and order in multiparty computation
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/99850 |
| _version_ | 1826197195978702848 |
|---|---|
| author | Park, Sunoo |
| author2 | Shafi Goldwasser. |
| author_facet | Shafi Goldwasser. Park, Sunoo |
| author_sort | Park, Sunoo |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. |
| first_indexed | 2024-09-23T10:44:17Z |
| format | Thesis |
| id | mit-1721.1/99850 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T10:44:17Z |
| publishDate | 2015 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/998502019-04-11T13:13:17Z On time and order in multiparty computation On time and order in MPC Park, Sunoo Shafi Goldwasser. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. Cataloged from PDF version of thesis. Includes bibliographical references (pages 65-66). The availability of vast amounts of data is changing how we can make medical discoveries, predict global market trends, save energy, improve our infrastructures, and develop new educational strategies. One obstacle to this revolution is the willingness of different entities to share their data with others. The theory of secure multiparty computation (MPC) allows parties to compute a function on their joint data while learning the minimum necessary information: the value of the function computed on their joint data (and nothing else). However, the theory of MPC does not address an important aspect: when do the players receive their outputs? In time-sensitive applications, the timing and order of outputs may be a crucial deciding factor in whether parties choose to share their data via the MPC. In this thesis, we incorporate time and order of output delivery into the theory of MPC. We first extend classical MPC to ordered MPC where different players receive their outputs according to an order which in itself is computed on the inputs to the protocol, and to refine the classical notions of guaranteed output delivery and fairness to require instead ordered output delivery and prefix-fairness. We then define timed-delay MPCs where explicit time delays are introduced into the output delivery schedule. We show general completeness theorems for ordered MPCs and timed-delay MPCs. We also introduce a new primitive called time-line puzzles, a natural extension of classical timed-release crypto in which multiple events can be serialized in time. Next, we show how ordered MPC can give rise to MPCs which are provably "worth" joining, in a range of collaborative situations. We formalize a model of collaboration and design a mechanism in which n self-interested parties can decide, based on their inputs, on an ordering of output delivery and a distribution of outputs to be delivered in the mandated order. The mechanism guarantees a higher reward for all participants by joining the ordered MPC, or declares that such a guarantee is impossible to achieve. We characterize the conditions under which this mechanism can be computed efficiently, and give a polynomial-time algorithm for such cases. by Sunoo Park. S.M. 2015-11-09T19:53:00Z 2015-11-09T19:53:00Z 2015 2015 Thesis http://hdl.handle.net/1721.1/99850 927414488 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 66 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Park, Sunoo On time and order in multiparty computation |
| title | On time and order in multiparty computation |
| title_full | On time and order in multiparty computation |
| title_fullStr | On time and order in multiparty computation |
| title_full_unstemmed | On time and order in multiparty computation |
| title_short | On time and order in multiparty computation |
| title_sort | on time and order in multiparty computation |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/99850 |
| work_keys_str_mv | AT parksunoo ontimeandorderinmultipartycomputation AT parksunoo ontimeandorderinmpc |