The emergence of cloud computing provides a new computing paradigm for users -- massive and complex computing tasks can be outsourced to cloud servers. However, the privacy issues also follow. Fully homomorphic encryption shows great potential in privacy-preserving computation, yet it is not ready for practice. At present, secure multiparty computation (MPC) remains mainly approach to deal with sensitive data. In this paper, following the secret sharing based MPC paradigm, we propose a secure 2-party computation scheme, in which cloud servers can securely evaluate functions with high efficiency. We first propose the multiplicative secret sharing (MSS) based on typical additive secret sharing (ASS). Then, we design protocols to switch shared secret between MSS and ASS, based on which a series of protocols for comparison and nearly all of the elementary functions are proposed. We prove that all the proposed protocols are Universally Composable secure in the honest-but-curious model. Finally, we will show the remarkable progress of our protocols on both communication efficiency and functionality completeness.
The emergence of cloud computing provides a new computing paradigm for users -- massive and complex computing tasks can be outsourced to cloud servers. However, the privacy issues also follow. Fully homomorphic encryption shows great potential in privacy-preserving computation, yet it is not ready for practice. At present, secure multiparty computation (MPC) remains mainly approach to deal with sensitive data. In this paper, following the secret sharing based MPC paradigm, we propose a secure 2-party computation scheme, in which cloud servers can securely evaluate functions with high efficiency. We first propose the multiplicative secret sharing (MSS) based on typical additive secret sharing (ASS). Then, we design protocols to switch shared secret between MSS and ASS, based on which a series of protocols for comparison and nearly all of the elementary functions are proposed. We prove that all the proposed protocols are Universally Composable secure in the honest-but-curious model. Finally, we will show the remarkable progress of our protocols on both communication efficiency and functionality completeness.
The rapid development of cloud computing has probably benefited each of us. However, the privacy risks brought by untrusty cloud servers arise the attention of more and more people and legislatures. In the last two decades, plenty of works seek the way of outsourcing various specific tasks while ensuring the security of private data. Although the addition and multiplication are enough for implementing any functions, the direct utilization of existing schemes like homomorphic encryption will lead to significant efficiency and accuracy loss, which is not suitable for outsourcing computation tasks. The tasks to be outsourced are endless, however, the involved calculations are similar. In this paper, inspired by additive secret sharing and multiplicative secret sharing technologies, we construct a series of novel protocols which support the common secure calculations on numbers (e.g., basic elementary functions) or matrices (e.g., solve eigenvectors) in arbitrary n number of servers (n≥2), and the n-party protocols ensure the security of the original data even if n−1 servers collude. All protocols we designed only need constant interaction rounds, and we demonstrate them under universally composability security. We believe that these protocols can provide a new basic tool for actual outsourced tasks.
We focus on how to securely outsource computation task to the cloud and propose a secure outsourcing multiparty computation protocol on lattice-based encrypted data in two-cloud-servers scenario. Our main idea is to transform the outsourced data respectively encrypted by different users' public keys to the ones that are encrypted by the same two private keys of the two assisted servers so that it is feasible to operate on the transformed ciphertexts to compute an encrypted result following the function to be computed. In order to keep the privacy of the result, the two servers cooperatively produce a custom-made result for each user that is authorized to get the result so that all authorized users can recover the desired result while other unauthorized ones including the two servers cannot. Compared with previous research, our protocol is completely noninteractive between any users, and both of the computation and the communication complexities of each user in our solution are independent of the computing function.
We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.
Outsourcing computation to cloud server has recently become popular in cloud computing. Cloud computing technologies enable clients with limited computational resources to outsource their massive computations to powerful cloud servers. Outsourcing computation has some new concerns, such as outsourced data and result privacy, verifiability and efficiency. Matrix multiplication is one of the most basic computational problems. In this paper, we are motivated to design a secure and efficient protocol for outsourcing the massive matrix multiplication computations to the cloud server. The existing works are mostly under amortized model that have an expensive phase as offline mode. Our proposed scheme does not have any expensive phase. So the client can outsource its matrices in online mode in which the efficiency of outsourcing will be increased. In our scheme, the client encrypts two matrices and sends them to a semi-honest cloud server. The cloud server computes matrix multiplication and a proof. After that, it sends the encrypted result to the client and finally the client checks the validity of the computation and decrypts the result. Our proposed scheme achieves privacy protection of outsourced data and multiplication result, unforgeability of proof, verification and high efficiency.
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.
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.