Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Dianzi xuebao

Efficient Secure Multiparty Computation Based on Homomorphic Encryption

Daoshun Wang

Published Jan 1, 2013• 4 citations
OpenAlex

Abstract

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.

Related papers

Secure multiparty computation for maximum and minimum values based on quantum homomorphic encryption

Shuang Li, Xiao‐Qiu Cai, Tian‐Yin Wang

Secure multiparty computation is a basic cryptographic primitive that has many important applications in privacy preservation. In this work, we propose a new secure multiparty computation protocol for the maximum and minimum values based on quantum homomorphic encryption. Owing to the speciality of quantum homomorphic encryption, participants can delegate a server to compute the maximum and minimum values of their private data. Furthermore, both calculations are performed on the encrypted data, and therefore the privacy of their respective private data can be perfectly guaranteed.

Optics Express•Mar 18, 2025•3 citations

Secure two party comparison over encrypted data

Parisa Kaghazgaran, Sadeghyan Babak

Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.

World Congress on Information and Communication Technologies•Dec 1, 2011•10 citations

Secure multi-party computation solution to Yao's millionaires' problem based on set-inclusion

Shundong Li, Dai Yiqi, You Qi-you

Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaries' problem have high computational complexity or communication complexity. In this study, based on the 1-out of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation patadigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.

Progress in Natural Science Materials International•Sep 1, 2005•4 citations

Efficient solution to the millionaires' problem based on asymmetric commutative encryption scheme

Meng Liu, Yun Luo, Priyadarsi Nanda +2 more

Abstract Secure multiparty computation is an important scheme in cryptography and can be applied in various real‐life problems. The first secure multiparty computation problem is the millionaires' problem, and its protocol is an important building block. Because of the less efficiency of public key encryption scheme, most existing solutions based on public key cryptography to this problem are inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. In this paper, we formally analyse the vulnerability of this solution, and propose a new scheme based on the decisional Diffie‐Hellman assumption. Our solution also uses 0‐encoding and 1‐encoding generated by our modified encoding method to reduce the computation cost. We implement the solution based on symmetric encryption scheme and our protocol. Extensive experiments are conducted to evaluate the efficiency of our solution, and the experimental results show that our solution can be much more efficient and be approximately 8000 times faster than the solution based on symmetric encryption scheme for a 32‐bit input and short‐term security. Moreover, our solution is also more efficient than the state‐of‐the‐art solution without precomputation and can also compare well with the state‐of‐the‐art protocol while the bit length of private inputs is large enough.

Computational Intelligence•May 23, 2019•4 citations

Efficient Protocols for the General Millionaires' Problem

Shundong Li, Yimin Guo, Sufang Zhou +2 more

Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.

Chinese Journal of Electronics•Jul 1, 2017•10 citations

Secure multiparty computation of a comparison problem

Xin Liu, Shundong Li, Jian Liu +2 more

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.

SpringerPlus•Sep 5, 2016•8 citations
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 multiparty computation is a basic cryptographic primitive that has many important applications in privacy preservation. In this work, we propose a new secure multiparty computation protocol for the maximum and minimum values based on quantum homomorphic encryption. Owing to the speciality of quantum homomorphic encryption, participants can delegate a server to compute the maximum and minimum values of their private data. Furthermore, both calculations are performed on the encrypted data, and therefore the privacy of their respective private data can be perfectly guaranteed.
Yao's classical millionaires' problem is about securely determining whether x>y, given two input values x, y, which are held as private inputs by two parties, respectively. The output which is result of comparison becomes known to both parties. In this paper we consider a variant of comparison problem in which the inputs x, y are encrypted and the actual values are not known to the parties. Our first solution deals with single comparison; however, in many applications, we encounter situations where it is necessary to make multiple comparisons to find the maximum among several encrypted data, so we make a modification to our first protocol to solve the multiple comparisons problem. Such a secure comparison is an important building block for applications like privacy preserving data mining and secure business. Our second protocol is based on Homomorphic encryption which achieves very low communication and computational complexities. Also our protocols can be performed in constant rounds and do not use general circuit evaluation techniques so they are more efficient than circuit based ones but not general. Implementation is easy and fast.
Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaries' problem have high computational complexity or communication complexity. In this study, based on the 1-out of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation patadigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.
Abstract Secure multiparty computation is an important scheme in cryptography and can be applied in various real‐life problems. The first secure multiparty computation problem is the millionaires' problem, and its protocol is an important building block. Because of the less efficiency of public key encryption scheme, most existing solutions based on public key cryptography to this problem are inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. In this paper, we formally analyse the vulnerability of this solution, and propose a new scheme based on the decisional Diffie‐Hellman assumption. Our solution also uses 0‐encoding and 1‐encoding generated by our modified encoding method to reduce the computation cost. We implement the solution based on symmetric encryption scheme and our protocol. Extensive experiments are conducted to evaluate the efficiency of our solution, and the experimental results show that our solution can be much more efficient and be approximately 8000 times faster than the solution based on symmetric encryption scheme for a 32‐bit input and short‐term security. Moreover, our solution is also more efficient than the state‐of‐the‐art solution without precomputation and can also compare well with the state‐of‐the‐art protocol while the bit length of private inputs is large enough.
Secure multiparty computation (SMC) is a research focusing in the international cryptographic community. The protocols used to address the millionaires' problem are the basic building blocks of most SMC protocols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all protocols used to address the millionaires' problem are based on integers, which means that their applications are limited. In this study, we propose precise and efficient protocols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computational geometry and it reduces the millionaires problem to computing the area of a triangle formed by three private points. This approach can determine whether the relationship between two private inputs is greater than, equal to or less than, and it has a much lower computational complexity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our approaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational geometry problem in rational number field.
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.