Nowadays, computation becomes more advanced, and may require more than one parties to participate.Some examples include e-voting system and privacy-preserving data analytics.One of the main concerns here is privacy.Inputs of these systems must be kept secret.To address this concern, we can construct the systems by using secure multi-party protocols, where several parties with their secret inputs perform joint computations in oblivious ways.Many aspects of the protocols can be further improved towards the usage in reallife applications, considering operational requirements and trade-offs.These operational requirements include efficiency, functionality, security, scalability, and verifiability.This thesis consists of three parts; each part focuses on specific improvements.In the first part, we focus on improving security and efficiency.We consider a homomorphic secret sharing scheme, where a secret input from each party is divided into several shares, each share is sent to different computing server, and the servers can perform some computation locally to get shares of the result.It is obvious that homomorphic secret sharing schemes can be used as secure multi-party protocols with small communication.We found that the existing homomorphic secret sharing scheme with public key of Lai et al. (Asiacrypt 2018) is 1-secure, which means if more than one computing servers try to collude, the security of the system will be compromised.They also proposed a t-secure scheme, but it requires solving NP-hard problem.To improve their security level, we use the idea from the secret sharing scheme of Ito et al.Our scheme also supports any number of computing servers without solving NP-hard problem.Using hyper-graph representation of non-access structures, we prove the maximum polynomial degree that our scheme can support.In addition, we prove correctness and security of the scheme, and propose some possible further improvements.In the second part, we focus on improving scalability and efficiency.Most of the secret sharing schemes, including homomorphic secret sharing, require the number of parties to be fixed in advance.This causes an inconvenience if we want to add more parties later in order to change the security setting or improve availability of the system.One existing variant of secret sharing, called evolving secret sharing, allows any number of parties to join the system at any time.However, it is inefficient to perform computation on this kind of secret sharing.To address this problem, we propose the definition of evolving homomorphic secret sharing, which combines evolving and homomorphic properties together.The scheme iii then supports unbounded number of parties, and allows local computation on shares.In addition to the definition, we propose two concrete schemes.The first scheme realizes evolving disjunctive hierarchical access structure supporting multiplication.The second scheme realizes evolving partially disjunctive hierarchical access structure supporting lowdegree polynomial computation.In the third part, we focus on improving functionality, verifiability, and efficiency.We consider the problem of oblivious deterministic finite automata (DFA) evaluation protocol.In this problem, one party holds a secret string, and the other party holds a secret pattern.The goal of this protocol is to output whether the string matches with the pattern of not without revealing both secret inputs.Most of the existing protocols use several communication rounds and require public key primitives, which can be inefficient.As our contribution, we propose an oblivious conditional disclosure of secrets (CDS) scheme for DFA.It is the first CDS scheme that has a functionality of DFA evaluation.We then use the proposed oblivious CDS scheme as a building block to construct an oblivious DFA evaluation protocol, using a multi-client verifiable computation framework.As a result, our protocol is constant-round, verifiable, and does not require any public key primitives.We also propose a standard CDS scheme for DFA as an independent interest.This thesis is expected to be a step of secure multi-party protocols and secret sharing schemes enhancements towards real-life applications.High level ideas for more improvements are also suggested as future prospects.
Nowadays, computation becomes more advanced, and may require more than one parties to participate.Some examples include e-voting system and privacy-preserving data analytics.One of the main concerns here is privacy.Inputs of these systems must be kept secret.To address this concern, we can construct the systems by using secure multi-party protocols, where several parties with their secret inputs perform joint computations in oblivious ways.Many aspects of the protocols can be further improved towards the usage in reallife applications, considering operational requirements and trade-offs.These operational requirements include efficiency, functionality, security, scalability, and verifiability.This thesis consists of three parts; each part focuses on specific improvements.In the first part, we focus on improving security and efficiency.We consider a homomorphic secret sharing scheme, where a secret input from each party is divided into several shares, each share is sent to different computing server, and the servers can perform some computation locally to get shares of the result.It is obvious that homomorphic secret sharing schemes can be used as secure multi-party protocols with small communication.We found that the existing homomorphic secret sharing scheme with public key of Lai et al. (Asiacrypt 2018) is 1-secure, which means if more than one computing servers try to collude, the security of the system will be compromised.They also proposed a t-secure scheme, but it requires solving NP-hard problem.To improve their security level, we use the idea from the secret sharing scheme of Ito et al.Our scheme also supports any number of computing servers without solving NP-hard problem.Using hyper-graph representation of non-access structures, we prove the maximum polynomial degree that our scheme can support.In addition, we prove correctness and security of the scheme, and propose some possible further improvements.In the second part, we focus on improving scalability and efficiency.Most of the secret sharing schemes, including homomorphic secret sharing, require the number of parties to be fixed in advance.This causes an inconvenience if we want to add more parties later in order to change the security setting or improve availability of the system.One existing variant of secret sharing, called evolving secret sharing, allows any number of parties to join the system at any time.However, it is inefficient to perform computation on this kind of secret sharing.To address this problem, we propose the definition of evolving homomorphic secret sharing, which combines evolving and homomorphic properties together.The scheme iii then supports unbounded number of parties, and allows local computation on shares.In addition to the definition, we propose two concrete schemes.The first scheme realizes evolving disjunctive hierarchical access structure supporting multiplication.The second scheme realizes evolving partially disjunctive hierarchical access structure supporting lowdegree polynomial computation.In the third part, we focus on improving functionality, verifiability, and efficiency.We consider the problem of oblivious deterministic finite automata (DFA) evaluation protocol.In this problem, one party holds a secret string, and the other party holds a secret pattern.The goal of this protocol is to output whether the string matches with the pattern of not without revealing both secret inputs.Most of the existing protocols use several communication rounds and require public key primitives, which can be inefficient.As our contribution, we propose an oblivious conditional disclosure of secrets (CDS) scheme for DFA.It is the first CDS scheme that has a functionality of DFA evaluation.We then use the proposed oblivious CDS scheme as a building block to construct an oblivious DFA evaluation protocol, using a multi-client verifiable computation framework.As a result, our protocol is constant-round, verifiable, and does not require any public key primitives.We also propose a standard CDS scheme for DFA as an independent interest.This thesis is expected to be a step of secure multi-party protocols and secret sharing schemes enhancements towards real-life applications.High level ideas for more improvements are also suggested as future prospects.
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)
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t < n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t < n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
Secure multi-party computation (MPC) is one of the most important primitives in cryptography. Several directions to construct and improve MPC protocols have been studied over the past decades. The majority of existing MPC protocols rely on assumptions such as every party communicates with every other party or every party needs to know every other party and the computation algorithm well in advance. Such assumptions can be difficult to achieve in modern large scale networks. This thesis explores two distinct lines of work leading to new practical models in response to these scenarios.First, we examine communication locality, the total number of other parties that each party communicates with in the protocol, as a new measure for an MPC protocol. Although progress has been made, the question of achieving low communication locality and round complexity at the same time for adaptive adversaries corrupting t l n/2 parties remains open. We show that by assuming a public-key infrastructure (PKI) and a symmetric-key infrastructure (SKI) the above question can be answered affirmatively, under standard assumptions. In particular, we describe a protocol with polylogarithmic communication locality and round complexity which tolerates up to t l n/2 adaptive corruptions. Our results are based on a new model of hidden random graphs obtained from the SKI, and using them to emulate a complete network in polylogarithmic rounds and polylogarithmic locality.We then examine multi-key fully homomorphic encryption (MFHE) schemes, which allow computation on data encrypted under different public keys chosen independently of each other. One of the main problems left in MFHE has been on how to deal with malicious users without trusted setup assumptions. We show how this can be done through circuit privacy, which guarantees that even if both ciphertexts and public keys are not well-formed, no information is revealed regarding the computation, other than what follows from the output on some well-formed inputs. Generalizing the result for circuit-private FHE, we provide a framework for adding circuit privacy to existing MFHE schemes.Finally, we incorporate the circuit privacy in a variant of server-assisted MPC, called on-the-fly MPC, where a server or a “cloud” performs an arbitrary dynamically chosen computation on a subset of data uploaded by multiple clients and encrypted under different keys on-the-fly. Circuit privacy allows the server to keep the algorithm used in the computation private even from a malicious adversary corrupting any number of clients. In particular, we construct a three-round on-the-fly MPC protocol with circuit privacy against malicious clients without the trusted setup.
Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open. We initiate a systematic study of HSS, making the following contributions. - A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework. - Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer. - Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.
ulti-Party Computation (MPC) protocols allow a set of mutually distrustful parties to securely compute on their joint private inputs, maintaining the privacy of those.Since its early conception in the eighties, a plethora of research as well as some real world deployments have taken place, demonstrating the relevance of such an interesting mathematical problem.Nevertheless, most of the research and all deployments have focused on scenarios where both the number of parties and network latency are very low.This thesis lays out the first steps towards practical deployments of large-scale MPC, where many parties may be involved and they might only be connected through a high-latency network such as the Internet.Both theoretical and empirical evidence shows that non-constant-round protocols cannot perform well on slow networks for many functions.In order to overcome this issue, all the works in this thesis include concretely efficient constant-round protocols based on multi-party garbled circuits.Chapter 3 and Chapter 4 deal with the very strong setting where an active adversary corrupts all but one parties.The former achieves such goal by using homomorphic encryption for low-depth circuits.The latter, based on subsequent work, improves the theoretical understanding of the problem and utilises oblivious transfer to improve efficiency.In Chapter 5 we provide both constant and non-constant round protocols that can handle large numbers of parties more efficiently.We leverage our performance improvements by relaxing the setting where all but one parties are corrupted to one where a small minority of honest participants can be assumed.Concretely, such change allows to distribute secret key material so that each party only holds a 'short' part of the key.Security is then based on the concatenation of all honest parties' keys rather than on each party's individual key, improving both the communication and computation complexities.iii researcher.They would have not been the same without the support of family, friends and colleagues.I would like to start by thanking Nigel Smart for giving me this opportunity, being my advisor and introducing me to others in the community.Martijn Stam
Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open.
We initiate a systematic study of HSS, making the following contributions.
- A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework.
- Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer.
- Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.