The multi-party comparing problem with no information leaking is generalized from the millionaires' problem, which is used to get whether these parties' secret inputs are all equal and if not, the number of users whose inputs are the same to a indicated user Pn's. Based on the semantic secure homomorphic encryption and the multi-threshold secret sharing scheme, a protocol of comparing multi-party information of equality is proposed. The correctness, security and efficiency are analyzed. The round complexity is two, the computation complexity is O(nk) modular exponentiations and the communication complexity is O(O2l) bits.
The multi-party comparing problem with no information leaking is generalized from the millionaires' problem, which is used to get whether these parties' secret inputs are all equal and if not, the number of users whose inputs are the same to a indicated user Pn's. Based on the semantic secure homomorphic encryption and the multi-threshold secret sharing scheme, a protocol of comparing multi-party information of equality is proposed. The correctness, security and efficiency are analyzed. The round complexity is two, the computation complexity is O(nk) modular exponentiations and the communication complexity is O(O2l) bits.
The secure multi-party comparing problem is generalized from the millionaires' problem,which is used to get whether the multi-party's secret inputs are all equal and if not,the number of users whose inputs are same as an indicated user's.Based on the F function and semantic addition homomorphic encryption,a protocol of secure multi-party comparing is proposed.The correctness,security and efficiency of the protocol are analyzed.This protocol can be used in many aspects of secure multi-party computation.
Secure multi-party ranking is a problem generalized from the millionaires' problem,which can be used by n people to know about their secrets' order among all their inputs without leaking further information.Through the study on millionaires' protocol,we presented a secure two-party ranking protocol under semi-honest model based on homomorphic encryption.Then we generalized it to secure multi-party ranking,and we presented two algorithms whose efficiency are both improved.Finally,we gave a secure multi-party ranking protocol based on fuzzy nearness degree,and we analyzed the efficiency and security of these protocols.
At present, research on secure multi-party computation is of great interest in modern cryptography. It should be acknowledged that if any function can be computed securely, then it results in a very powerful tool. In fact, all natural protocols are, or can be rephrased to be, special cases of the multi-party computation problems. Design and analysis of the special multi-party computation protocols is meaningful and has attracted much interest in this field. Based on the combination of a public-key cryptosystem of the homomorphic encryption and on the theoretic construction relying on the F-hiding assumption, a protocol for comparing information of equality is proposed. The protocol needs only a single round of interaction and ensures fairness, efficiency and security. The protocol is fair, which means that one party knows the sound result of the comparison if and only if the other one knows the result. The protocol is efficient with the help of an oblivious third party for calculating. However, the third party cannot learn any information about the participant抯 private inputs and even about the comparison result, and cannot collude with any participant. The protocol is secure for the two participants, that is, any information about their secret input will not leak except the final computation result. A precise proof of security of the protocol is presented. Applications of this protocol may include private bidding and auctions, secret ballot elections, commercial business, identification in a number of scenarios and so on. It is believed that the protocol may be of practical significance for electronic transaction.
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.
Secure multi-party computation is a hot research topic in cryptography in recent years, and has become an important research direction in cryptography. This paper studies the millionaires’ problem in secure multi-party computation, and its essence is a comparison issue about the size of two encrypted data. Yao offered a solution to the millionaires’ problem, but his protocol can’t accurately compare two numbers. We improved Yao’s protocol and proposed two generic protocols to solve the millionaires’ problem. Our first protocol has one more round of communication between participants than Yao’s, but our protocol can accurately compare the size of two numbers. The second protocol improved the first protocol, and only one round of communication is needed to get accurate comparison results. Finally, we realized the second protocol based on RSA encryption algorithm, and analyze the security under the semi-honest model.
In this paper, we study a secure multi-party ranking problem: there are n parties, P1, P2, ... , Pn. Each party Pihas a secret input miisin {1, 2, ... ,N}. He wants to get the order of miin the ascending ranking sequence of the n parties' inputs, while not leaking the value of mi. This problem extends the famous Yao's millionaires' problem form two parties to n parties and is a multi-party Yao's Millionaires' problem. We propose a protocol for solving the secure multi-party ranking problem, using the encoding scheme and the El Gamal cryptosystem. We also prove the correctness and the security of our solution in the semi-honest model. The solution of secure multi-party ranking problem can make new-style electronic transactions, such as private bidding and auction, secret online transaction and so on, become better security.