An efficient two party RSA secret key sharing generation scheme based on a homomorphic encryption, which is semantically secure under the prime residuosity assumption, is proposed in this paper. At the stage of computing RSA modulo N , an initial distributed primality test protocol is used to reduce the computation complexity and increase the probability of N being a two-prime product. On the other aspect, the homomorphic encryption based sharing conversion protocols is devised and adopted in multi-party computing modulus N and secret key d . Comparing to any sharing conversion protocols based on oblivious transfer protocol, the homomorphic encryption based sharing conversion protocols are of high performance. Our scheme resists the passive attack and since a method of verifying the sharing was introduced in, the scheme can resists any cheating behaviors too. Security proof, computation complexity and communication complexity analysis are given at last.
An efficient two party RSA secret key sharing generation scheme based on a homomorphic encryption, which is semantically secure under the prime residuosity assumption, is proposed in this paper. At the stage of computing RSA modulo N , an initial distributed primality test protocol is used to reduce the computation complexity and increase the probability of N being a two-prime product. On the other aspect, the homomorphic encryption based sharing conversion protocols is devised and adopted in multi-party computing modulus N and secret key d . Comparing to any sharing conversion protocols based on oblivious transfer protocol, the homomorphic encryption based sharing conversion protocols are of high performance. Our scheme resists the passive attack and since a method of verifying the sharing was introduced in, the scheme can resists any cheating behaviors too. Security proof, computation complexity and communication complexity analysis are given at last.
The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999 ) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: ( i ) a distributed protocol for generation of an RSA composite and ( ii ) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: ( i ) a distributed generation of the corresponding secret key shares and ( ii ) a distributed decryption protocol for decrypting according to Paillier.
The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is complete Paillier [Pai99] threshold encryption scheme in the two-party setting with security against malicious behavior. Furthermore, we describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation is comprised of the following: (i) a distributed protocol for generation of an RSA composite, and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite as public key and is comprised of: (i) a distributed generation of the corresponding secret-key shares and, (ii) a distributed decryption protocol for decrypting according to Paillier.
Secure multi-party multiplication is a special secure multi-party computation problem, which can be used by multi-party to share the multiplication result. Present protocols frequently using the secure two-party multiplication protocol which has high communication cost and large amount of data. Based on the homomorphic encryption technology, a serial secure multi-party multiplication protocol in the complex communication environment and a parallel secure multi-party multiplication protocol in the ideal communication environment are presented for this problem in the semi-honest model.At last, correctness and security of those protocols are analyzed. Compared with the present protocols, the analysis shows that the proposed protocols have better advantages in the communication cost and the execution 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.
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.
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).