Negotiations using secure multi-party computation
(2015)
Files
these.pdf
Open Access - Adobe PDF
- 815.08 KB
Details
- Authors
- Supervisors
- Pereira, Olivier
- Abstract
- Secure multi-party computation is a problem where a number of parties want to compute a function of their inputs in a secure way. Security implies correctness of the outputs and privacy of the inputs, even when some parties are cheating. This problem has been at the centre of cryptography research for almost 30 years. However, it is only recently that practical applications have been developed, for example, in auctions, voting systems or data mining. In this vein, this thesis aims to securely solve classical algorithmic problems using multi-party computation techniques, but departs from the traditional focus on problems that admit a simple circuit representation to investigate problems with a richer structure. First, this work presents new sorting algorithms based on a unary representation of integers. These algorithms can be used efficiently as subroutines for applications that make use of the unary representation, for example, in addressing mechanisms. Second, a new procedure to obtain a fair division of a heterogeneous resource between competing parties is provided. This procedure does not have a counterpart in game theory and the equilibrium reached dominates the ones that were previously known in unmediated procedures. Finally, the first secure single-source shortest path and maximum flow algorithms are developed. Depending on the settings, these algorithms raise intriguing questions in terms of asymptotic complexity compared to their traditional counterparts.
- Affiliations
Citations
Mawet, S. (2015). Negotiations using secure multi-party computation. https://hdl.handle.net/2078.5/187933