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

Journal of Convergence Information Technology

Improvement of a Secure Convex Hull Two-Party Computation Protocol

Zhao Wenjie -, Mingxing He

Published May 26, 2010• 2 citations
Publisher

Abstract

In 2008, Wang et. al. first investigate a sort of specific secure multi-party computation--secure convex hull two-party computation, and construct two protocols based on Gift wrapping method and Quick method separately. However, there are some errors in his protocol based on Quick method. This paper proposes two effective improved protocols. In addition, we analyze and compare security, computational complexity and communicational complexity about these two improved protocols.

DOI
10.4156/jcit.vol5.issue3.4

Related papers

An efficient and secure multi-party convex hull protocol using quantum secret commitment

Wen-Jie Liu, Solomon Danquah Danso

Convex hull computation is a fundamental problem in secure multi-party computational geometry (SMCG), classified under secure multi-party computation (SMC) for finding the convex hull of a set of points. Existing quantum solutions largely depend on quantum homomorphic encryption (QHE), which introduces significant computational overhead due to frequent key updates by a trusted third party (TTP). Furthermore, most current protocols lack a mechanism for input commitment, making them vulnerable to post-computation input tampering or denial by the TTP. To overcome these limitations, we propose an efficient convex hull protocol that utilizes quantum secret commitment (QSC) as a more secure alternative to QHE. Our protocol enables a designated party (the committer) to securely commit to input values in a manner that guarantees both binding (no post-hoc alteration) and hiding (input secrecy). We introduce a novel value comparison protocol within an Ideal Quantum K-Party model, ensuring privacy-preserving convex hull computation without reliance on QHE. Rigorous security analysis demonstrates significant improvements in computational efficiency and resilience against quantum adversaries. Our protocol represents a pivotal advancement for quantum-secure multi-party computations and lays the groundwork for scalable, future-proof privacy-preserving geometry in quantum computing contexts.

EPJ Quantum Technology•Feb 23, 2026•0 citations

A protocol of specific secure two-party computation

Bao Li

The research of multi-party computation was a subject of great importance in the international cryptographic circle. Based on the Φ-hiding assumption and public-key cryptosystem of homomprphic encryption, we constructed a protocol of special secure two-party computation--comparing protocol. The protocol could ensure fairness, security, efficiency and robustness. We also proved the security and correctness of the protocol, using the strict definition of the secure multi-party computation. Applications of the protocol included private bidding and auctions, secret ballot elections and so on.

Journal of China Institute of Communications•Jan 1, 2004•4 citations

Quantum secure multi-party computational geometry based on multi-party summation and multiplication

Zhao Dou, Yifei Wang, Zhaoqian Liu +3 more

Abstract Secure multi-party computational geometry is a branch of secure multi-party computation, which is applied in many important fields. But up to now, the research on how to solve this problem with quantum methods has just started. Therefore, we study the design of quantum secure multi-party computational geometry (QSMCG) protocols in this paper. As the foundation, we extend the two-party summation and multiplication protocols proposed by Sutradhar and Om to multi-party protocols. Then we propose three new QSMCG protocols. Our proposed quantum secure two-party distance computation protocol has improvement in efficiency and accuracy. And the proposed quantum secure multi-party polytope volume computation protocol as well as the quantum secure circle–circle intersection area computation protocol are designed for the first time. Moreover, these protocols are designed to use multi-third parties, which solves the problem of intermediate value leakage in computation. The correctness, security and performance of all these protocols are analyzed.

Quantum Science and Technology•Mar 18, 2024•9 citations

A spatial crowdsourced single-point collaborative convex hull computation protocol based on quantum homomorphic encryption

Bai Liu, Xinguo Wang, Run-Hua SHI +1 more

Abstract With the growing demand for location privacy protection and collaborative computing in spatial crowdsourcing (SC) tasks, traditional encryption methods based on computational complexity face threats from quantum computing and efficiency bottlenecks. To address this, this paper proposes a secure multi-party quantum comparison (SMQC) protocol based on quantum homomorphic encryption. By utilizing a quantum comparator and a key update mechanism, this protocol enables secure comparison of numerical values among multiple parties while maintaining encryption. Building on this foundation, the SMQC protocol is further applied to the SC environment to construct a single-point collaborative convex hull computation protocol. Through extreme point determination and convex hull boundary verification, this protocol efficiently performs multi-party collaborative convex hull computation while protecting the location privacy of participants. Analysis indicates that the convex hull computation framework built on this protocol is reliable and secure, further expanding the application of quantum-secure solutions in SC scenarios such as single-point collaborative obstacle avoidance and collaborative spatial protection.

Physica Scripta•Aug 6, 2026•0 citations

Improved Protocol of Yao’s Millionaires Problem

Huiqiang Li, Zhengtao Jiang, Ting Yu +1 more

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.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•Jun 26, 2022•2 citations

Round efficient computationally secure multi-party computation revisited

Laasya Bangalore, Ashish Choudhury, Gayathri Garimella

In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.

International Conference on Distributed Computing and Networking (ICDCN)•Jan 4, 2019•3 citations
In 2008, Wang et. al. first investigate a sort of specific secure multi-party computation--secure convex hull two-party computation, and construct two protocols based on Gift wrapping method and Quick method separately. However, there are some errors in his protocol based on Quick method. This paper proposes two effective improved protocols. In addition, we analyze and compare security, computational complexity and communicational complexity about these two improved protocols.
Convex hull computation is a fundamental problem in secure multi-party computational geometry (SMCG), classified under secure multi-party computation (SMC) for finding the convex hull of a set of points. Existing quantum solutions largely depend on quantum homomorphic encryption (QHE), which introduces significant computational overhead due to frequent key updates by a trusted third party (TTP). Furthermore, most current protocols lack a mechanism for input commitment, making them vulnerable to post-computation input tampering or denial by the TTP. To overcome these limitations, we propose an efficient convex hull protocol that utilizes quantum secret commitment (QSC) as a more secure alternative to QHE. Our protocol enables a designated party (the committer) to securely commit to input values in a manner that guarantees both binding (no post-hoc alteration) and hiding (input secrecy). We introduce a novel value comparison protocol within an Ideal Quantum K-Party model, ensuring privacy-preserving convex hull computation without reliance on QHE. Rigorous security analysis demonstrates significant improvements in computational efficiency and resilience against quantum adversaries. Our protocol represents a pivotal advancement for quantum-secure multi-party computations and lays the groundwork for scalable, future-proof privacy-preserving geometry in quantum computing contexts.
The research of multi-party computation was a subject of great importance in the international cryptographic circle. Based on the Φ-hiding assumption and public-key cryptosystem of homomprphic encryption, we constructed a protocol of special secure two-party computation--comparing protocol. The protocol could ensure fairness, security, efficiency and robustness. We also proved the security and correctness of the protocol, using the strict definition of the secure multi-party computation. Applications of the protocol included private bidding and auctions, secret ballot elections and so on.
Abstract Secure multi-party computational geometry is a branch of secure multi-party computation, which is applied in many important fields. But up to now, the research on how to solve this problem with quantum methods has just started. Therefore, we study the design of quantum secure multi-party computational geometry (QSMCG) protocols in this paper. As the foundation, we extend the two-party summation and multiplication protocols proposed by Sutradhar and Om to multi-party protocols. Then we propose three new QSMCG protocols. Our proposed quantum secure two-party distance computation protocol has improvement in efficiency and accuracy. And the proposed quantum secure multi-party polytope volume computation protocol as well as the quantum secure circle–circle intersection area computation protocol are designed for the first time. Moreover, these protocols are designed to use multi-third parties, which solves the problem of intermediate value leakage in computation. The correctness, security and performance of all these protocols are analyzed.
Abstract With the growing demand for location privacy protection and collaborative computing in spatial crowdsourcing (SC) tasks, traditional encryption methods based on computational complexity face threats from quantum computing and efficiency bottlenecks. To address this, this paper proposes a secure multi-party quantum comparison (SMQC) protocol based on quantum homomorphic encryption. By utilizing a quantum comparator and a key update mechanism, this protocol enables secure comparison of numerical values among multiple parties while maintaining encryption. Building on this foundation, the SMQC protocol is further applied to the SC environment to construct a single-point collaborative convex hull computation protocol. Through extreme point determination and convex hull boundary verification, this protocol efficiently performs multi-party collaborative convex hull computation while protecting the location privacy of participants. Analysis indicates that the convex hull computation framework built on this protocol is reliable and secure, further expanding the application of quantum-secure solutions in SC scenarios such as single-point collaborative obstacle avoidance and collaborative spatial protection.
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 work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.