Secure two-party computation allows two mutually distrusting parties to compute a joint function over their inputs, guaranteeing properties such as \emph{input privacy} or \emph{correctness}. For many tasks, such as joint computation of statistics, it is important that when one party receives the result of the computation, the other party also receives the result. Unfortunately, this property, which is called \emph{fairness}, is unattainable in the two-party setting for arbitrary functions. So weaker variants have been proposed. One such notion, proposed by Pass \etal (EUROCRYPT 2017) is called \emph{
Δ-fairness}. Informally, it guarantees that if a corrupt party receives the output in round
r and stops participating in the protocol, then the honest party receives the output by round
Δ(r). This notion is achieved by using so-called \emph{secure enclaves}. In many settings,
Δ-fairness is not sufficient, because a corrupt party is \emph{guaranteed} to receive its output before the honest party, giving the corrupt party an advantage in further interaction. Worse, as
Δ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of
Δ-fairness by introducing a new fairness notion, which we call \emph{hidden
Δ-fairness}, which addresses these problems. First of all, under our new notion, a corrupt party may not benefit from aborting, because it may not, with probability $\nicefrac{1}{2}$, learn the result first. Moreover,
Δ and other parameters are sampled according to a given distribution and remain unknown to the participants in the computation. We propose a 2PC protocol that achieves hidden
Δ-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.
In the problem of Secure Multi-party Computation, the objective is to design a protocol that allows a group of parties to securely compute functions of their collective private data, while ensuring that no party reveals any more information about its private data other than what must be inherently revealed by the computation results (privacy) and that no parties can disrupt or influence the computation results beyond the effects of changing their input data (correctness and consistency). Information theoretic approaches toward this problem, that provide provable (unconditional) security guarantees even against adversarial parties that have unbounded computational power, have established that general computation is possible in a variety of scenarios. However, these general solutions are not always efficient or finely tuned to the requirements of specific problems and applications.
The focus of this thesis is on the development of information theoretic approaches for multi-party computation applications with the common theme of secure and efficient computation and inference over a distributed data network. Specific applications include: 1) private information retrieval, where the objective is to privately retrieve data without revealing what was selected; 2) secure statistical analysis, the problem of extracting statistics without revealing anything else about the underlying data; 3) secure sampling, which is the secure generation of new data with a given distribution; and 4) secure authentication, where the identity of a party needs to authenticated via inference on his/her credentials and stored registration data.
The contributions of this thesis toward addressing these applications include the following: The development of an Oblivious Transfer (OT) protocol, applicable to private information retrieval, that trades off a small amount of privacy while being several times more efficient than other OT protocols. The efficiency of general se- cure two-party computation via OT realized from noisy channels is also analyzed. A technique for approximate secure multi-party computation applicable to secure statistical analysis of large scale distributed databases is developed. By exploiting a dimensionality reduction and the structure of a broad class of functions based on the computed statistics, the feasibility of simultaneously achieving both arbitrarily high accuracy and arbitrarily high communication efficiency is demonstrated. The region of distributions that can be securely sampled in the two-party scenario is characterized. It is further established that for those distributions, it can be accomplished with a protocol that only sends one message. Inner and outer bounds on the region of distributions that can be securely sampled in the general multi-party scenario are also developed. A new three-party protocol, applicable to the problem of secure biometric authentication, that securely computes the Hamming distance even when one of the parties arbitrarily deviates from the protocol is proposed and analyzed. A two-factor secure biometric authentication system that is robust against the compromise of registered biometric data, allowing for revocability and resistance against cross-enrollment attacks is also proposed.