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.
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.
In this thesis we focus on various aspects of secure message transmission protocols. Such protocols achieve the secure transmission of a message from a sender to a receiver - where the term “secure” encapsulates the notion of privacy and reliability of message transmission. These two parties are connected using an underlying network in which a static computationally unlimited active adversary able to corrupt up to t network nodes is assumed to be present. Such protocols are important to study as they are used extensively in various cryptographic protocols and are of interest to other research areas such as ad-hoc networks, military networks amongst others. Optimal bounds for the number of phases (communication from sender to receiver or vice versa), connectivity requirements (number of node disjoint network paths connecting sender and receiver - denoted by n), communication complexity (complexity of the number of field elements sent - where F is the finite field used and jFj = q) and transmission complexity (proportion of communication complexity to complexity of secrets transmitted) for secure message transmission protocols have been proven in previous work. In the one-phase model it has been shown that n 3t+1 node disjoint paths are required to achieve perfect communication. In the two phase model only n 2t + 1 node disjoint paths are necessary. This connectivity is also the required bound for almost perfectly secure one-phase protocols - protocols which achieve perfect privacy but with a negligible probability may fail to achieve reliability. In such cases the receiver accepts a different message to that transmitted by the sender or does not accept any message. The main focus of recent research in secure message transmission protocols has been to present new protocols which achieve optimal transmission complexity. This has been achieved through the transmission of multiple messages. If a protocol has a communication complexity of O(n3) field elements, to achieve optimal transmission complexity O(n2) secrets will have to be communicated. This has somewhat ignored the simplification and improvement of protocols which securely transmit a single secret. Such improvements include constructing more efficient protocols with regards to communication complexity, computational complexity and the number of field elements sent throughout the whole protocol. In the thesis we first consider one-phase almost perfectly secure message transmission and present two new protocols which improve on previous work. We present a polynomial time protocol of O(n2) communication complexity which at the time of writing this thesis, is computationally more efficient than any other protocol of similar communication complexity for the almost perfectly secure transmission of a single message. Even though our first almost perfectly secure transmission protocol is of polynomial time, it is important to study other protocols also and improve previous work presented by other researchers. This is the idea behind the second one-phase almost perfectly secure message transmission protocol we present which requires an exponential complexity of field operations but lower (O(n)) communication complexity. This protocol also improves on previous protocols of similar communication complexity, requiring in the order of O(log q) less computation to complete - where q denotes the size of the finite field used. Even though this protocol is of exponential time, for small values of n (e.g. when t = 1, t = 2 or t = 3) it may be beneficial to use this protocol for almost perfectly secure communication as opposed to using the polynomial time protocol. This is because less field elements need to be transmitted over the whole network which connects a sender and a receiver. Furthermore, an optimal almost perfectly secure transmission protocol will be one with O(n) communication complexity and with polynomial computational complexity. We hope that in the future, other researchers will be inspired by our proposed protocol, improve on our work and ideally achieve these optimal results. We also consider multi-phase protocols. By combining various cryptographic schemes, we present a new two-phase perfectly secure single message transmission protocol. At the time of writing this thesis, the protocol is the most efficient protocol when considering communication complexity. Our protocol has a communication complexity of O(n2) compared to O(n3) of previous work thus improving on the communication complexity by an order of O(n) for the perfectly secure message transmission of a single message. This protocol is then extended to a three phase protocol where a multi-recipient broadcast end channel network setting is considered. As opposed to point to point networks where a path from a sender reaches a single receiver, this network model is new in the field of message transmission protocols. In this model each path from a sender reaches multiple receivers, with all receivers receiving the same information from their common network communication channel. We show how the use of this protocol upon such a network can lead to great savings in the transmission and computation carried out by a single sender. We also discuss the importance and relevance of such a multi-recipient setting to practical applications. The first protocols in the field of perfectly secure message transmission with a human receiver are also presented. This is a topic proposed by my supervisor Professor Yvo Desmedt for which I constructed solutions. In such protocols, one of the communicating parties is considered to be a human who does not have access to a computational device. Because of this, solutions for such protocols need to be computationally efficient and computationally simple so that they can be executed by the human party. Experiments with human participants were carried out to assess how easily and accurately human parties used the proposed protocols. The experimental results are presented and these identify how well human participants used the protocols. In addition to the security of messages, we also consider how one can achieve anonymity of message transmission protocols. For such protocols, considering a single-receiver multi-sender scenario, the presence of a t-threshold bounded adversary and the transmission of multiple secrets (as many as the number of sender), once the protocols ends one should not be able to identify the sender of a received message. Considering a passive and active adversary new protocols are presented which achieve the secure and anonymous transmission of messages in the information-theoretic security model. Our proposed solutions can also be applied (with minor alterations) to the dual problem when a single-sender multi-recipient communication setting is considered. The contributions of the thesis are primarily theoretical - thus no implementation of the proposed protocols was carried out. Despite this, we reflect on practical aspects of secure message transmission protocols. We review the feasibility of implementing secure message transmission protocols in general upon various networks - focusing on the Internet which can be considered as the most important communication network at this time. We also describe in theory how concepts of secure message transmission protocols could possibly be used in practical implementations for secure communication on various existing communication networks. Open problems that remain unsolved in the research area of the proposed protocols are also discussed and we hope that these inspire research and future solutions for the design (and implementation) of better and more efficient secure message transmission protocols.
Cryptography grew to be much more than "the study of secret writing". Modern cryptography is concerned with establishing properties such as privacy, integrity and authenticity in protocols for secure communication and computation. This comes at a price: Cryptographic tools usually introduce an overhead, both in terms of communication complexity (that is, number and size of messages transmitted) and computational efficiency (that is, time and memory required). As in many settings communication between the parties involved is the bottleneck, this thesis is concerned with improving communication complexity in cryptographic protocols. One direction towards this goal is scalable cryptography: In many cryptographic schemes currently deployed, the security degrades linearly with the number of instances (e.g. encrypted messages) in the system. As this number can be huge in contexts like cloud computing, the parameters of the scheme have to be chosen considerably larger - and in particular depending on the expected number of instances in the system - to maintain security guarantees. We advance the state-of-the-art regarding scalable cryptography by constructing schemes where the security guarantees are independent of the number of instances. This allows to choose smaller parameters, even when the expected number of instances is immense. - We construct the first scalable encryption scheme with security against active adversaries which has both compact public keys and ciphertexts. In particular, we significantly reduce the size of the public key to only about 3% of the key-size of the previously most efficient scalable encryption scheme. (Gay,Hofheinz, and Kohl, CRYPTO, 2017) - We present a scalable structure-preserving signature scheme which improves both in terms of public-key and signature size compared to the previously best construction to about 40% and 56% of the sizes, respectively. (Gay, Hofheinz, Kohl, and Pan, EUROCRYPT, 2018) Another important area of cryptography is secure multi-party computation, where the goal is to jointly evaluate some function while keeping each party’s input private. In traditional approaches towards secure multi-party computation either the communication complexity scales linearly in the size of the function, or the computational efficiency is poor. To overcome this issue, Boyle, Gilboa, and Ishai (CRYPTO, 2016) introduced the notion of homomorphic secret sharing. Here, inputs are shared between parties such that each party does not learn anything about the input, and such that the parties can locally evaluate functions on the shares. Homomorphic secret sharing implies secure computation where the communication complexity only depends on the size of the inputs, which is typically much smaller than the size of the function. A different approach towards efficient secure computation is to split the protocol into an input-independent preprocessing phase, where long correlated strings are generated, and a very efficient online phase. One example for a useful correlation are authenticated Beaver triples, which allow to perform efficient multiplications in the online phase such that privacy of the inputs is preserved and parties deviating the protocol can be detected. The currently most efficient protocols implementing the preprocessing phase require communication linear in the number of triples to be generated. This results typically in high communication costs, as the online phase requires at least one authenticated Beaver triple per multiplication. We advance the state-of-the art regarding efficient protocols for secure computation with low communication complexity as follows. - We construct the first homomorphic secret sharing scheme for computing arbitrary functions in NC 1 (that is, functions that are computably by circuits with logarithmic depth) which supports message spaces of arbitrary size, has only negligible correctness error, and does not require expensive multiplication on ciphertexts. (Boyle, Kohl, and Scholl, EUROCRYPT, 2019) - We introduce the notion of a pseudorandom correlation generator for general correlations. Pseudorandom correlation generators allow to locally extend short correlated seeds into long pseudorandom correlated strings. We show that pseudorandom correlation generators can replace the preprocessing phase in many protocols, leading to a preprocessing phase with sublinear communication complexity. We show connections to homomorphic secret sharing schemes and give the first instantiation of pseudorandom correlation generators for authenticated Beaver triples at reasonable computational efficiency. (Boyle, Couteau, Gilboa, Ishai, Kohl, and Scholl, CRYPTO, 2019)
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
Secure multi-party computation (MPC) enables mutually distrusting parties to compute functions over private inputs without revealing additional information. A general MPC protocol is the one that can be used to securely compute any function. General MPC requires either an honest majority or oblivious transfer, which can be provided via computational assumptions, a black-box hybrid, or trusted hardware. However, in the setting of dishonest majority, there are still many tasks that can be computed securely in the information-theoretic plain model without relying on oblivious transfer or any other computational hardness assumptions. Such protocols are perfectly secure, fast, and do not require any setup or preprocessing.This thesis investigates the feasibility and complexity of secure two-party computation, which inherently falls under the dishonest majority setting, with randomized output in the information-theoretic plain model against honest-but-curious adversaries. For deterministic output functions, seminal work by Chor, Kushilevitz, and Beaver provided a complete characterization of which computations admit secure protocols. In contrast, randomized functionalities give rise to a substantially richer landscape, where questions of round complexity, communication complexity, and even decidability have remained unresolved for decades.The thesis develops a geometric framework for analyzing secure computation by encoding candidate private-coin secure protocols for a given functionality as points in high-dimensional spaces. Within this representation, the space of all secure protocols forms recursively defined geometric sets whose structure can be studied using tools from real algebraic geometry and convex analysis. This perspective enables feasibility, search, and optimization problems in secure computation to be reduced to structural properties of these sets.Using this framework, the thesis establishes that determining whether a given two-party functionality with randomized output admits a secure protocol is decidable. A finite procedure is provided that either constructs a secure protocol with optimal round and communication complexity or identifies a geometric obstruction to security, resolving a foundational open problem in secure computation and information complexity. These results rely on showing that certain lamination hulls arising in the analysis are semi-algebraic, which is achieved by reducing the problem to solving systems of linear inequalities over convex sets. To this end, the thesis introduces a Gaussian-elimination-inspired algorithm and a new set operator, the positive geometric join, leading to a class of algebraically well-behaved geometric objects called hemihedra.The thesis also studies the round and communication complexity of secure computation with randomized output and disproves a longstanding folklore conjecture asserting that round complexity depends only on the cardinalities of the input and output domains. Explicit constructions demonstrate the existence of securely realizable functions with arbitrarily high round complexity, even for fixed size inputs and outputs, while matching upper bounds are proved for small output alphabets. These results reveal a close connection between secure computation and lamination hulls originally studied in hydrodynamics, highlighting unexpected geometric structure underlying information-theoretic security.
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation.
In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results.
The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation.
The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.
In this work, we investigate the security of interactive computations. The main emphasis is on the mathematical methodology that is needed to formalise and analyse various security properties. Differently from many classical treatments of secure multi-party computations, we always quantify security in exact terms. Although working with concrete time bounds and success probabilities is technically more demanding, it also has several advantages. As all security guarantees are quantitative, we can always compare different protocol designs. Moreover, these security guarantees also have a clear economical interpretation and it is possible to compare cryptographic and non-cryptographic solutions. The latter is extremely important in practice, since cryptographic techniques are just one possibility to achieve practical security. Also, working with exact bounds makes reasoning errors more apparent, as security proofs are less abstract and it is easier to locate false claims. The choice of topics covered in this thesis was guided by two principles. Firstly, we wanted to give a coherent overview of the secure multi-party computation that is based on exact quantification of security guarantees. Secondly, we focused on topics that emerged from the author's own research. In that sense, the thesis generalises many methodological discoveries made by the author. As surprising as it may seem, security definitions and proofs mostly utilise principles of hypothesis testing and analysis of stochastic algorithms. Thus, we start our treatment with hypothesis testing and its generalisations. In particular, we show how to quantify various security properties, using security games as tools. Next, we review basic proof techniques and explain how to structure complex proofs so they become easily verifiable. In a nutshell, we describe how to represent a proof as a game tree, where each edge corresponds to an elementary proof step. As a result, one can first verify the overall structure of a proof by looking at the syntactic changes in the game tree and only then verify all individual proof steps corresponding to the edges. The remaining part of the thesis is dedicated to various aspects of protocol design. Firstly, we discuss how to formalise various security goals, such as input-privacy, output-consistency and complete security, and how to choose a security goal that is appropriate for a specific setting. Secondly, we also explore alternatives to exact security. More precisely, we analyse connections between exact and asymptotic security models and rigorously formalise a notion of subjective security. Thirdly, we study in which conditions protocols preserve their security guarantees and how to safely combine several protocols. Although composability results are common knowledge, we look at them from a slightly different angle. Namely, it is irrational to design universally composable protocols at any cost; instead, we should design computationally efficient protocols with minimal usage restrictions. Thus, we propose a three-stage design procedure that leads to modular security proofs and minimises usage restrictions.