Private comparison is fundamental to secure multiparty computation. In this study, we propose novel protocols to privately determine [Formula: see text], or [Formula: see text] in one execution. First, a 0-1-vector encoding method is introduced to encode a number into a vector, and the Goldwasser-Micali encryption scheme is used to compare integers privately. Then, we propose a protocol by using a geometric method to compare rational numbers privately, and the protocol is information-theoretical secure. Using the simulation paradigm, we prove the privacy-preserving property of our protocols in the semi-honest model. The complexity analysis shows that our protocols are more efficient than previous solutions.
Private comparison is fundamental to secure multiparty computation. In this study, we propose novel protocols to privately determine [Formula: see text], or [Formula: see text] in one execution. First, a 0-1-vector encoding method is introduced to encode a number into a vector, and the Goldwasser-Micali encryption scheme is used to compare integers privately. Then, we propose a protocol by using a geometric method to compare rational numbers privately, and the protocol is information-theoretical secure. Using the simulation paradigm, we prove the privacy-preserving property of our protocols in the semi-honest model. The complexity analysis shows that our protocols are more efficient than previous solutions.
Many privacy protections in distributed setting are based on secure comparison, according to which two distrusted users try to jointly determine whether a > b, a = b, or a1)/(kb + k1)), which implies the potential relationship (a > b, a = b, and a1, and b belong to the party who doesn't have the secret of the system. Based on this system, two distrusted users in distributed setting can learn whether a > b, a = b, or a <; b in one execution, without disclosing a and b to each other. Then, we develop two efficient protocols for secure comparison on integers and secure comparison on fractions, respectively. Our schemes, based on homomorphic encryption, are cryptographically secure. We prove that these protocols are secure using simulation paradigm. Our approaches can be used in many secure multi-party computation protocols that involve fractions, rational numbers, and integers. They can also be more convenient to solve some secure multiparty computational geometry problems that often involve ratio evaluation.
As a fundamental part of cryptography, secure multiparty computation (SMC) is a building block of various cryptographic protocols, and it is also a hot topic in the international cryptographic community.In recent years, many SMC problems, such as secret information comparison, secret set problems and secure multiparty computational geometry, have been widely studied.As many practical problems need to be described by rational numbers, it is both theoretically and practically important to study the SMC problems in the rational number field.However, most of the existing researches focus on integers and the studied data are mainly one-dimensional data.There are few researches on secure multiparty computation of multi-dimensional data in the rational number field, but they can’t be generalized.Based on the fractional representation of rational numbers, the new encoding schemes about rational numbers and rational number vectors were proposed, which could encode multi-dimensional data in the rational number field and provided new solutions for other SMC problems in the rational number field.Based on the encoding scheme and one-way hash function, some protocols were designed for equality problems and set problems in the rational number field.These protocols used basic arithmetic operation and hash operation to guarantee efficiency than existing related protocols.And these protocols didn’t limit the range of research data and they were more widely applicable.It proves that these protocols are secure in the semi-honest model using simulation paradigm, and demonstrates the efficiency and the applicability of these protocols by theoretical analysis and experiment.A practical example was also given to illustrate that approaches are more versatile, and they could also be directly used to solve some secure multiparty computational geometry problems in the rational number field.
Private integer comparison has been an essential computation function for many applications, including online auction, credential identification, data mining, and joint bidding. In the setting of two-party computation, two parties with private inputs (x and y) want to jointly compare them without revealing the value of those inputs to others (also known as the Millionaires’ problem) while the output should ensure correctness and preserve data privacy. The private inputs only can be revealed if they are equal, i.e., x = y. Many related works have been proposed to solve the integer comparison problem in various settings, focusing on different properties such as round and computation complexity. Most solutions decompose integers into bitwise representation and then securely evaluate the function in a Boolean circuit on encrypted bits. However, this type of solution is costly (especially for large integers) as each bit requires encryption and decryption. In this paper, we transform the private integer comparison into a block comparison problem. In particular, we employ a block vectorization mechanism to encode the private inputs into blocks. We show the security of our two-party protocol in the semi-honest model. Also, we implement the protocol to demonstrate its efficiency using block vectorization mechanism and homomorphic encryption. The experimental result proves that our proposed solution achieves high efficiency, particularly for large integer comparisons.
Secure multiparty computation is a key privacy-preserving technology in cyberspaces and a research focus in the international cryptographic community.We first present a new encoding scheme to encode private data.By using this encoding scheme together with homomorphic encryption scheme,we construct a new scheme for Yao′s millionaires′ problem and prove its privacy-preserving property.This new scheme is more concise,more general and can be applied to compare any two objects on which a total order can be defined.We finally utilize the new scheme to propose a solution to the coprime problem and prove the privacy-preserving properties of the solution.
Secure comparison is a fundamental problem in multiparty computation. There are two different parties, each holding an l-bit integer, denoted by a and b, respectively. The goal of secure comparison is to compute the order relationship between a and b, say (a>b)∈{0,1}, without revealing their inputs to any others. Since previous solutions based on homomorphic encryption need at least Ω(l) encryptions for each l-bit comparison, the total encryption time leads to a computational bottleneck for these protocols. This work presents a fast, semi-honest, secure comparison protocol based on the BFV encryption scheme. With its vector-like plaintext space, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity O˜(λ+l) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08 ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of l⋅k−1-bit integers with almost the same execution time as comparing l-bit integers and achieve higher throughput regardless of the compared integer size.
Secure multiparty computation is valuable for studying data privacy protection issues due to its decentralization, input privacy, fairness, etc. One of the most fundamental problems is to confidentially compute the maximum and the minimum of multiple data. In this paper, an efficient secure multipart computation scheme that can compute the maximum and the minimum simultaneously without a trusted third party was proposed to address the problems of existing secure multi-party computation protocols, such as inability of computing the maximum and the minimum at one time, low efficiency, and security risks caused by unique designated decryption key holder. In the scheme, an encoding method that can simultaneously compute the maximum and the minimum was first provided, whose basic idea was to give a complete set of ordinal numbers with potential l (l ≥ the number of participants n), and each participant encodes its data into an array with length l where the location of the data in the complete set was coded as a random number and the other positions were coded as 1. The positions of the leftmost and rightmost non-1 values in the product array were the positions of the maximum and minimum in the whole set. Based on the proposed encoding method, the ElGamal homomorphic encryption algorithm was used to guarantee the confidentiality of all participants’ data, and the maximum threshold decryption was used to make each participant hold part of the decryption key, which avoids the security threats caused by centralized decryption of calculation result by designated key holder. The proposed scheme was proven to be resistant to collusive attacks by any participant under a semi-honest model based on an ideal-realistic simulation paradigm. Finally, the efficiency analysis and performance comparison with related maximum (minimum) computing schemes were given, which showed that the proposed protocol has advantages over existing schemes in terms of computational complexity and communication complexity under the premise of higher security.