A Shannon Approach to Secure Multi-party Computations
This work addresses secure computation problems for parties needing to compute functions on private data without revealing extra information, but it appears incremental as it builds on existing Shannon and SMC frameworks.
The paper tackles secure multi-party computations by investigating Shannon-type questions in two models: a one-shot model without data priors, focusing on randomness cost and capacity, and a probabilistic model with data correlations, focusing on dependency for secure function computation, using polar code constructions for summation functions.
In secure multi-party computations (SMC), parties wish to compute a function on their private data without revealing more information about their data than what the function reveals. In this paper, we investigate two Shannon-type questions on this problem. We first consider the traditional one-shot model for SMC which does not assume a probabilistic prior on the data. In this model, private communication and randomness are the key enablers to secure computing, and we investigate a notion of randomness cost and capacity. We then move to a probabilistic model for the data, and propose a Shannon model for discrete memoryless SMC. In this model, correlations among data are the key enablers for secure computing, and we investigate a notion of dependency which permits the secure computation of a function. While the models and questions are general, this paper focuses on summation functions, and relies on polar code constructions.