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

IEEE International Conference on Acoustics Speech and Signal Processing

Efficient multi-party computation with collusion-deterred secret sharing

Zhaohong Wang, Ying Luo, Sen-ching S. Cheung

Published May 1, 2014• 12 citations
Publisher

Abstract

Many secure multiparty computation (SMC) protocols use Shamir's Secret Sharing (SSS) scheme as a building block. Unlike other cryptographic SMC techniques such as garbled circuits (GC), SSS requires no data expansion and achieves information theoretic security. A weakness of SSS is the possibility of collusion attacks from participants. In this paper, we propose an evolutionary game-theoretic (EGT) approach to deter collusion in SSS-based protocols. First, we consider the possibility of detecting the leak of secret data caused by collusion, devise an explicit retaliation mechanism, and show that the evolutionary stable strategy of this game is not to collude if the technology to detect the leakage of secret is readily available. Then, we consider the situation in which data-owners are unaware of the leakage and thereby unable to retaliate. Such behaviors are deterred by injecting occasional fake collusion requests, and detected by a censorship scheme that destroys subliminal communication. Comparison results show that our collusion-deterred SSS system significantly outperforms GC, while game simulations confirm the validity of our EGT framework on modeling collusion behaviors.

DOI
10.1109/icassp.2014.6855038

Related papers

Quantum-Inspired Cryptographic Protocols for Secure Multi-Party Computation

Jincheng Zhang

This paper investigates the application of quantum-inspired cryptographic principles to enhance the security and efficiency of secure multi-party computation (SMC) protocols. Traditional SMC protocols, such as Shamir's Secret Sharing, rely on classical cryptographic assumptions that are increasingly vulnerable to advancements in computing power, particularly with the rise of quantum computers. We propose a framework leveraging concepts from quantum mechanics, specifically superposition and probabilistic approaches, to construct novel SMC protocols. These protocols aim to achieve comparable security levels to existing methods while potentially offering improved performance characteristics and resilience against attacks exploiting classical vulnerabilities. The core of our approach involves replacing deterministic operations with probabilistic ones, mimicking the inherent uncertainty in quantum systems. This reduces the reliance on hard mathematical problems and introduces a layer of complexity that is more difficult for adversaries to analyze. The paper details the design of a modified Shamir Secret Sharing scheme incorporating these quantum-inspired elements and provides a theoretical analysis of its security properties. Ultimately, this work contributes to the exploration of a new paradigm in cryptography, adapting quantum-inspired techniques to bolster the security of distributed computing environments.

•Sep 7, 2026•0 citations

Secure Multi-Party Computation

Fattaneh Bayatbabolghani, Marina Blanton

Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•25 citations

Combining shamir and additive secret sharing to improve efficiency of SMC primitives against malicious adversaries

Kenneth Richard Goss

Secure multi-party computation provides a wide array of protocols for mutually distrustful parties be able to securely evaluate functions of private inputs. Within recent years, many such protocols have been proposed representing a plethora of strategies to securely and efficiently handle such computation. These protocols have become increasingly efficient, but their performance still is impractical in many settings. We propose new approaches to some of these problems which are either more efficient than previous works within the same security models or offer better security guarantees with comparable efficiency. The goals of this research are to improve efficiency and security of secure multi-party protocols and explore the application of such approaches to novel threat scenarios. Some of the novel optimizations employed are dynamically switching domains of shared secrets, asymmetric computations, and advantageous functional transformations, among others. Specifically, this work presents a novel combination of Shamir and Additive secret sharing to be used in parallel which allows for the transformation of efficient protocols secure against passive adversaries to be secure against active adversaries. From this set of primitives we propose the construction of a comparison protocol which can be implemented under that approach with a complexity which is more efficient than other recent works for common domains of interest. Finally, we present a system which addresses a critical security threat for the protection and obfuscation of information which may be of high consequence.

arXiv:2311.08934•Jan 1, 2020•0 citations

Collusion-Secure Semi-Quantum Secret Sharing Scheme using a Quantum Third Party

Santanu Majhi, Nirupam Basak

The security of a secret sharing protocol is compromised if one or more dishonest participants can reconstruct the secret by deviating from the prescribed protocol, particularly when such malicious behavior remains undetected. Semi-Quantum Secret Sharing (SQSS) is a variant of secret sharing in which the participants possess only classical capabilities, such as preparing and measuring qubits in the computational ($Z$) basis, while a quantum-capable third party assists the dealer in generating and distributing quantum shares of a classical secret. The limited quantum capabilities of the participants in SQSS protocols may introduce vulnerabilities to collusion attacks, enabling an assisting quantum third party, in collaboration with a dishonest classical participant, to jointly recover the secret even without detection. In this work, we propose a novel SQSS protocol that eliminates this vulnerability and achieves information-theoretic security against collusion attacks. We further prove that the proposed protocol is secure against a broad class of external and internal attacks. Finally, a comparative analysis demonstrates that our construction advances existing SQSS protocols by simultaneously optimizing qubit efficiency, involves a classical dealer, and resilience against DCNA attacks using basic Bell states.

cs.CRCross-listedarXiv:2610.10176•Oct 8, 2026•1 citation

Implementation of a Secure Multiparty Computation Protocol

Tahsin C. M. Dönmez

Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.

•Dec 20, 2017•0 citations

Leakage-Resilient Secret Sharing Against Colluding Parties

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.

Annual Symposium on Foundations of Computer Science•Nov 1, 2019•34 citations
Many secure multiparty computation (SMC) protocols use Shamir's Secret Sharing (SSS) scheme as a building block. Unlike other cryptographic SMC techniques such as garbled circuits (GC), SSS requires no data expansion and achieves information theoretic security. A weakness of SSS is the possibility of collusion attacks from participants. In this paper, we propose an evolutionary game-theoretic (EGT) approach to deter collusion in SSS-based protocols. First, we consider the possibility of detecting the leak of secret data caused by collusion, devise an explicit retaliation mechanism, and show that the evolutionary stable strategy of this game is not to collude if the technology to detect the leakage of secret is readily available. Then, we consider the situation in which data-owners are unaware of the leakage and thereby unable to retaliate. Such behaviors are deterred by injecting occasional fake collusion requests, and detected by a censorship scheme that destroys subliminal communication. Comparison results show that our collusion-deterred SSS system significantly outperforms GC, while game simulations confirm the validity of our EGT framework on modeling collusion behaviors.
This paper investigates the application of quantum-inspired cryptographic principles to enhance the security and efficiency of secure multi-party computation (SMC) protocols. Traditional SMC protocols, such as Shamir's Secret Sharing, rely on classical cryptographic assumptions that are increasingly vulnerable to advancements in computing power, particularly with the rise of quantum computers. We propose a framework leveraging concepts from quantum mechanics, specifically superposition and probabilistic approaches, to construct novel SMC protocols. These protocols aim to achieve comparable security levels to existing methods while potentially offering improved performance characteristics and resilience against attacks exploiting classical vulnerabilities. The core of our approach involves replacing deterministic operations with probabilistic ones, mimicking the inherent uncertainty in quantum systems. This reduces the reliance on hard mathematical problems and introduces a layer of complexity that is more difficult for adversaries to analyze. The paper details the design of a modified Shamir Secret Sharing scheme incorporating these quantum-inspired elements and provides a theoretical analysis of its security properties. Ultimately, this work contributes to the exploration of a new paradigm in cryptography, adapting quantum-inspired techniques to bolster the security of distributed computing environments.
Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.
Secure multi-party computation provides a wide array of protocols for mutually distrustful parties be able to securely evaluate functions of private inputs. Within recent years, many such protocols have been proposed representing a plethora of strategies to securely and efficiently handle such computation. These protocols have become increasingly efficient, but their performance still is impractical in many settings. We propose new approaches to some of these problems which are either more efficient than previous works within the same security models or offer better security guarantees with comparable efficiency. The goals of this research are to improve efficiency and security of secure multi-party protocols and explore the application of such approaches to novel threat scenarios. Some of the novel optimizations employed are dynamically switching domains of shared secrets, asymmetric computations, and advantageous functional transformations, among others. Specifically, this work presents a novel combination of Shamir and Additive secret sharing to be used in parallel which allows for the transformation of efficient protocols secure against passive adversaries to be secure against active adversaries. From this set of primitives we propose the construction of a comparison protocol which can be implemented under that approach with a complexity which is more efficient than other recent works for common domains of interest. Finally, we present a system which addresses a critical security threat for the protection and obfuscation of information which may be of high consequence.
The security of a secret sharing protocol is compromised if one or more dishonest participants can reconstruct the secret by deviating from the prescribed protocol, particularly when such malicious behavior remains undetected. Semi-Quantum Secret Sharing (SQSS) is a variant of secret sharing in which the participants possess only classical capabilities, such as preparing and measuring qubits in the computational (ZZZ) basis, while a quantum-capable third party assists the dealer in generating and distributing quantum shares of a classical secret. The limited quantum capabilities of the participants in SQSS protocols may introduce vulnerabilities to collusion attacks, enabling an assisting quantum third party, in collaboration with a dishonest classical participant, to jointly recover the secret even without detection. In this work, we propose a novel SQSS protocol that eliminates this vulnerability and achieves information-theoretic security against collusion attacks. We further prove that the proposed protocol is secure against a broad class of external and internal attacks. Finally, a comparative analysis demonstrates that our construction advances existing SQSS protocols by simultaneously optimizing qubit efficiency, involves a classical dealer, and resilience against DCNA attacks using basic Bell states.
Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.
In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.