Abstract
This thesis contains research on the theory of secure multi-party computation (MPC).
Especially information theoretically (as opposed to computationally) secure protocols.
It contains results from two main lines of work.
One line on Information Theoretically Secure Oblivious RAMS, and how they are used to speed up secure computation.
An Oblivious RAM is a construction for a client with a small $O(1)$ internal memory to store $N$ pieces of data on a server while revealing nothing more than the size of the memory $N$, and the number of accesses. This specifically includes hiding the access pattern.
We construct an oblivious RAM that hides the client's access pattern with information theoretic security with an amortized $\log^3 N$ query overhead. And how to employ a second server that is guaranteed not to conspire with the first to improve the overhead to $\log^2 N$, while also avoiding the bottleneck of sorting networks. And we show how to utilize this construction for four-player MPC.
Another line of work has results about the power of correlated randomness; meaning in a preprocessing phase the participants in a MPC protocol receive samples from some joint distribution to aid them implement the secure computation. Especially we look at the communication complexity of protocols in this model, and perfectly secure protocols.
We show general protocols for any finite functionality with statistical security and optimal communication complexity (but exponential amount of preprocessing). And for two-player functionalities where only one player receives output (sender-receiver functionalities) with perfect security.
We also show protocols for some specific sender-receiver tasks with both optimal communication and small preprocessing.
We show lower bounds on the amount of communication and show the impossibility of general perfect protocols when both parties receive output.
Also we show how to use the sender-receiver protocols with perfect security given correlated randomness to construct secure protocols in the plain model with perfect correctness
Especially information theoretically (as opposed to computationally) secure protocols.
It contains results from two main lines of work.
One line on Information Theoretically Secure Oblivious RAMS, and how they are used to speed up secure computation.
An Oblivious RAM is a construction for a client with a small $O(1)$ internal memory to store $N$ pieces of data on a server while revealing nothing more than the size of the memory $N$, and the number of accesses. This specifically includes hiding the access pattern.
We construct an oblivious RAM that hides the client's access pattern with information theoretic security with an amortized $\log^3 N$ query overhead. And how to employ a second server that is guaranteed not to conspire with the first to improve the overhead to $\log^2 N$, while also avoiding the bottleneck of sorting networks. And we show how to utilize this construction for four-player MPC.
Another line of work has results about the power of correlated randomness; meaning in a preprocessing phase the participants in a MPC protocol receive samples from some joint distribution to aid them implement the secure computation. Especially we look at the communication complexity of protocols in this model, and perfectly secure protocols.
We show general protocols for any finite functionality with statistical security and optimal communication complexity (but exponential amount of preprocessing). And for two-player functionalities where only one player receives output (sender-receiver functionalities) with perfect security.
We also show protocols for some specific sender-receiver tasks with both optimal communication and small preprocessing.
We show lower bounds on the amount of communication and show the impossibility of general perfect protocols when both parties receive output.
Also we show how to use the sender-receiver protocols with perfect security given correlated randomness to construct secure protocols in the plain model with perfect correctness
| Original language | English |
|---|
| Publisher | Institut for Datalogi, Aarhus Universitet |
|---|---|
| Number of pages | 119 |
| Publication status | Published - 2013 |