The thesis deals with a subfield of cryptography called secure multi-party computation which is a technique that allows multiple parties to work together to compute a single function while preserving the privacy of it's inputs. More specifically, the thesis deals with secure multi-party computation over the ring of integers modulo pk . The thesis begins with an introduction of the general principle of secure multi-party protocols, followed by the construction of the necessary theoretical groundwork over commutative rings, wich will be needed to describe and understand a specific protocol in the last section of the thesis. 1
The thesis deals with a subfield of cryptography called secure multi-party computation which is a technique that allows multiple parties to work together to compute a single function while preserving the privacy of it's inputs. More specifically, the thesis deals with secure multi-party computation over the ring of integers modulo pk . The thesis begins with an introduction of the general principle of secure multi-party protocols, followed by the construction of the necessary theoretical groundwork over commutative rings, wich will be needed to describe and understand a specific protocol in the last section of the thesis. 1
The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.
This thesis discusses new results in two areas within cryptography; securely transmitting a message between two parties and securely computing a function on the inputs of multiple parties. For both of these areas we mainly consider perfectly secure protocols, which are protocols that have a zero error probability and that do not rely on any number-theoretical assumptions for their security or correctness.
For the first area, we in this thesis give an overview of all results on perfectly secure message transmission in the commonly used model and furthermore determine the exact achievable communication complexity under the weakest possible assumption in this model. For the second area, which is commonly referred to as secure multi-party computation, we introduce new techniques that allow to drastically reduce the required communication for perfectly secure multi-party computations and establish new connections with coding theory and algebraic geometry.
Secure computation involves multiple parties computing a common function while keeping their inputs private, and is a growing field of cryptography due to its potential for maintaining privacy guarantees in real-world applications. However, current secure computation protocols are not yet efficient enough to be used in practice. We argue that this is due to much of the research effort being focused on generality rather than specificity. Namely, current research tends to focus on constructing and improving protocols for the strongest notions of security or for an arbitrary number of parties. However, in real-world deployments, these security notions are often too strong, or the number of parties running a protocol would be smaller. In this thesis we make several steps towards bridging the efficiency gap of secure computation by focusing on constructing efficient protocols for specific real-world settings and security models. In particular, we make the following four contributions: - We show an efficient (when amortized over multiple runs) maliciously secure two-party secure computation (2PC) protocol in the multiple-execution setting, where the same function is computed multiple times by the same pair of parties. - We improve the efficiency of 2PC protocols in the publicly verifiable covert security model, where a party can cheat with some probability but if it gets caught then the honest party obtains a certificate proving that the given party cheated. - We show how to optimize existing 2PC protocols when the function to be computed includes predicate checks on its inputs. - We demonstrate an efficient maliciously secure protocol in the three-party setting.
We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z # p for q|p 1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).
A secure multi-party computation problem deals with computing a function on any input, in a distributed network, ensuring that no more information is revealed to a player in the computation. New protocols are developed for the following interesting variation on a typical problem of secure multi-party computation: Given secrets shared among a group of players, compute the function value of basic computations, such as interpolation, addition, multiplication or inversion, in the exponent. The protocols can be proven robust and secure in standard computation models.
We present general definitions of security for multi-party cryptographic protocols, with focus on the task of evaluating a probabilistic function of the parties' inputs. We show that, with respect to these definitions, security is preserved under a natural composition operation. The definitions follow the general paradigm of known definitions; yet some substantial modifications and simplifications are introduced. The composition operation is the natural `subroutine substitution' operation, formalized by Micali and Rogaway. We consider several standard settings for multi-party protocols, including the cases of eavesdropping, Byzantine, non-adaptive and adaptive adversaries, as well as the information-theoretic and the computational models. In particular, in the computational model we provide the first definition of security of protocols that is shown to be preserved under composition.