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

International Symposium on Information Theory and its Applications

Client-Aided Bit-Composition Protocol with Guaranteed Output Delivery

Hikaru Tsuchida, Takashi Nishide

Published Oct 24, 2020• 0 citations
OpenAlex

Abstract

Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.

Related papers

Client-aided Robust Bit-composition Protocol with Deterministic Cheater Identification in Standard Model

Hikaru Tsuchida, Takashi Nishide

Secure multiparty computation (MPC) enables parties to compute an arbitrary function without revealing each party's inputs. A typical MPC is secret-sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that look exactly like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is a bit-composition protocol that converts a k-dimensional vector with shares on ℤ2 (i.e., shares of binary sequence) to shares on ℤ2k (i.e., shares of decimal value). Previous studies proposed a maliciously secure bit-composition protocol with robustness, which is a security notion that all parties learn the correct output regardless of the attacker's behaviour. However, its security is dependent on a statistical parameter or proved in the random oracle model. In this paper, we propose a novel bit-composition protocol with robustness independent of a statistical parameter by introducing additional clients generating the pair of shares of random values only in the offline phase (which can be performed without the parties' inputs). Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is a weaker assumption than the random oracle model). Our protocol achieves efficiency and the strongest security simultaneously. We also propose a protocol for the Hamming distance with robustness by modifying our bit-composition protocol. It can achieve a secure iris recognition service via MPC with robustness. Furthermore, we extend our protocol with a constant number of parties and clients to one with an arbitrary number of parties and clients.

Journal of Information Processing•Jan 1, 2021•0 citations

Secure Computation with Partial Message Loss

Chiu‐Yuen Koo

Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 1

•Feb 6, 2008•0 citations

Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority

Anders Dalskov, Daniel E. Escudero, Ariel Nof

We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating t < n/3 active corruptions whileguaranteeing output delivery (G.O.D.). Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties n. However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is constant, except for a light constant-round check that is performed at the end before revealing the output.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 7, 2022•20 citations

Secure Multiparty Computation with Dynamic Participants and Guaranteed Output

Giovanni Deligios

Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.

•Jan 1, 2025•0 citations

Committed MPC

Tore Kasper Frederiksen, Benny Pinkas B, Avishay Yanai

We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

Lecture notes in computer science•Jan 1, 2018•22 citations

Towards High-Throughput Secure MPC over the Internet: Communication-Efficient Two-Party Protocols and Its Application

Satsuya Ohata, Koji Nuida

Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits, some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. This is less than a half compared with the previous work. Moreover, the number of communication bits is also $38.4\%$ fewer. As a result, total online execution time is $56.1\%$ shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.

•Jul 8, 2019•1 citation
Secure multiparty computation (MPC) enables par-ties to compute an arbitrary function without revealing each party’s inputs. A typical MPC is the secret sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that just look like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is the bit-composition protocol that converts a k-dimensional vector with the shares on Z 2 (i.e., shares of binary sequence) to the shares on Z 2 k (i.e., shares of decimal value). The previous work proposed a maliciously secure bit-composition protocol with guaranteed output delivery (GOD), which is the security notion that all the parties learn the correct output regardless of the attacker’s behaviour. However, its security is proved in the random oracle model.In this paper, we propose a new bit-composition protocol with GOD by introducing additional clients just helping the parties during computation. Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is weaker than the random oracle model). Our protocol achieves the efficiency and strongest security simultaneously. We also propose a protocol for the Hamming distance with GOD by modifying our bit-composition protocol. It achieves a secure iris recognition service via MPC with GOD.
Secure multiparty computation (MPC) enables parties to compute an arbitrary function without revealing each party's inputs. A typical MPC is secret-sharing based MPC (SS-MPC). In the SS-MPC, each party distributes its inputs, and the computation proceeds with secret shares that look exactly like random numbers distributed among the parties. In the SS-MPC protocol, the parties can compute any function represented as a circuit by using shares locally and communicating among the parties. In particular, when the parties compute a complex function composed of binary and arithmetic circuits, an efficient share conversion protocol facilitates the computation of it. An important conversion protocol is a bit-composition protocol that converts a k-dimensional vector with shares on ℤ2 (i.e., shares of binary sequence) to shares on ℤ2k (i.e., shares of decimal value). Previous studies proposed a maliciously secure bit-composition protocol with robustness, which is a security notion that all parties learn the correct output regardless of the attacker's behaviour. However, its security is dependent on a statistical parameter or proved in the random oracle model. In this paper, we propose a novel bit-composition protocol with robustness independent of a statistical parameter by introducing additional clients generating the pair of shares of random values only in the offline phase (which can be performed without the parties' inputs). Our protocol is based on a maliciously secure four-party protocol with one corruption using replicated secret sharing. The security of our protocol is proved in the standard model (which is a weaker assumption than the random oracle model). Our protocol achieves efficiency and the strongest security simultaneously. We also propose a protocol for the Hamming distance with robustness by modifying our bit-composition protocol. It can achieve a secure iris recognition service via MPC with robustness. Furthermore, we extend our protocol with a constant number of parties and clients to one with an arbitrary number of parties and clients.
Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 1
We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating t < n/3 active corruptions whileguaranteeing output delivery (G.O.D.). Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties n. However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is constant, except for a light constant-round check that is performed at the end before revealing the output.
Secure Multiparty Computation (MPC) is an expression encompassing cryptographic techniques that allow mutually distrustful parties to jointly perform computations over private data, ensuring correctness and preserving privacy despite malicious behavior. Guaranteed output is the strongest security goal for MPC: protocols with this property always deliver results. This is in contrast with weaker notions that allow malicious aborts. The seminal works of Ben-Or, Goldwasser, and Wigderson (STOC’88) and Rabin and Ben-Or (STOC’89) showed interactive protocols to compute any function with guaranteed output and perfect security if fewer than one third of parties are corrupted, or with statistical security (with a small error probability) if fewer than half are corrupted. These results hold when the set of participants is fixed throughout the execution. Ostrovsky and Yung’s proactive model (PODC’91) relaxes this assumption by allowing the set of corrupted parties to evolve over time, better capturing the dynamics of long-lived computations, where machines may be periodically compromised and recovered. The recent YOSO (You Only Speak Once) and fluid MPC models (CRYPTO’21) push this ambitious modelling even further by allowing for fully dynamic participation, with parties joining and leaving the computation at will. In this setting, known protocols with guaranteed output fall short of optimal resilience or rely on non-standard communication and adversarial assumptions. Matching the classical BGW and Rabin–Ben-Or bounds in these settings remained an open problem. We resolve these questions within the Layered MPC abstraction of David et al. (CRYPTO’23), in which the interaction pattern of a protocol is restricted to be a layered graph, meaning parties are partitioned into a sequence of disjoint sets (layers) and can send private and broadcast messages to parties in immediately subsequent layers. We match the BGW and Rabin and Ben-Or bounds in this model, fully characterizing the feasibility landscape of Layered MPC with guaranteed output. As a stepping stone towards our statistically secure protocol, we construct a more efficient and conceptually simpler computationally secure protocol relying on linear non-interactive commitments. Our results yield optimally-resilient and maximally-proactive MPC protocols with guaranteed output for both perfect and statistical security.
We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.
Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits, some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. This is less than a half compared with the previous work. Moreover, the number of communication bits is also 38.4%38.4\%38.4% fewer. As a result, total online execution time is 56.1%56.1\%56.1% shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.