Privacy and utility in secure computations: optimal trade-offs through quantitative information flow

Secure Multi-Party Computation is a domain of Cryptography that enables several participants to compute a public function of their own private inputs, while preserving the secrecy of the inputs and without resorting to any trusted third party. Elaborate protocols have been designed in order to help participants to collaborate in order to compute functions in such a way. These protocols ensure that no information about the private inputs is ever revealed, apart from that which flows from the public and intended output of the computation. Intriguingly, the output of a computation, as a function of the inputs, inevitably leaks some information about the private inputs. The main objectives of this thesis are to further investigate this inevitable information flow, to propose a means of quantifying this leakage and to alleviate the risks it may generate. We introduce an attacker model based on a family of entropy-based measures that enable us to formally quantify the information that can be inferred about private inputs in secure computations. The measure of information flow that we use generalises and unifies the notions of Rényi entropy and g-entropy. Based on this model, we design randomising mechanisms that aim at enhancing participants' privacy by introducing a perturbation on function outputs, while guaranteeing a maximal distortion bound. We formally investigate optimal trade-offs between privacy of inputs and utility of output under different assumptions. We develop techniques that realise such trade-offs, which involve solving non-linear and non-convex optimisation problems as well as designing greedy and dynamic algorithms. We experimentally highlight the privacy gains that the solutions we obtain provide. Finally, we demonstrate that our analyses may scale to arbitrarily large input spaces in specific and well-defined applications by examining the special cases of secure three-party affine computations and digital goods auctions. We conclude by discussing this scalability issue along with the adaptation of our approach to continuous input spaces, which we believe may seed interesting prospects.Open Acces