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

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Packed Linear Secret Sharing-Based Simultaneous Multiplication and Comparison

Shohei MITA, Kazuki Yoneyama

Published Jun 4, 2026• 0 citations
Publisher

Abstract

Performing L pairs of multiplication with known (k, n)-linear secret sharing-based n party multiplication protocols using an (offline) preprocessing by the Beaver multiplication triple requires 2Lk elements of on-line communications where k is the threshold. This paper proposes a simultaneous multiplication protocol for L pairs based on (k, L, n)-packed linear secret sharing. By embedding L secret information into each share using (k, L, n)-packed linear secret sharing, though partial information of secret information is leaked from k - l + 1 shares for 1 ≤ l ≤ L, the proposed protocol can perform L multiplications with 2k elements of online communications. As applications of the proposed simultaneous multiplication protocol, we also introduce a simultaneous comparison protocol and an improvement of the communication cost of Araki et al.'s n party group-wise maximum/minimum value aggregation protocol. For example, when computing the maximum/minimum value of eight 64-bit data, our proposed aggregation protocol can reduce 59.6% of the communication cost.

DOI
10.1587/transfun.2025eap1180

Related papers

An Efficient Framework for Unconditionally Secure Multiparty Computation

Ashish Choudhury, Arpita Patra

parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.

IEEE Transactions on Information Theory•Oct 4, 2016•63 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

Efficient Three-party Boolean-to-Arithmetic Share Conversion

Nan Cheng, Feng Zhang, Aikaterini Mitrokotsa

The advantage of mixed-protocol multi-party secure computation frameworks lies in their ability to utilize different sharing types optimally for diverse tasks. A key module in these frameworks are Boolean-to-arithmetic secret sharing conversion protocols, which transfer a secret value from Boolean secret sharing to arithmetic secret sharing. This conversion process can either take in the Boolean secret sharing of a bit or a secret binary string. In this work, we suggest the application of an innovative correlated random tuple for this task in the semi-honest three-party (3PC) setting. This tuple provides the basis for building Boolean-to-arithmetic share conversion protocols. Specifically, we propose two such protocols in the semi-honest 3PC setting, the first protocol takes as input the Boolean secret sharing of a bit, and the second protocol takes as input the Boolean secret sharing of a secret binary string. When it comes to concrete efficiency, the first protocol shows superior performance compared to the existing state-of-the-art in ABY3 (CCS ’18). It achieves this by reducing the total required communication from 2ℓ bits per party to 4ℓ/3+1 bits (including 4ℓ/3 bits in the setup phase, and 1 bit in the online phase) per party, while maintaining a single round of optimized communication. On the other hand, the second protocol involves two rounds of online communication and its communication cost is comparable to that of ABY2.0 (USENIX’21) that relies on correlated oblivious transfer.

Conference on Privacy, Security and Trust•Aug 21, 2023•3 citations

Constrained Multiplication Protocol on Replicated Secret Sharing with Application to Modulus Conversion and Bit Decomposition

Hiroki Sudo, Ryo Kikuchi, Koki Hamada +1 more

In the context of secret-sharing-based secure multiparty computation, multiplication is a fundamental operation. To date, multiplication protocols with reduced communication have been actively studied, and recent works have achieved one-round multiplication with each party sending only a single element. In this work, we propose a constrained multiplication protocol. While our protocol is applicable only in constrained situations, it reduces the total communication in practical applications to one third to one third of that of such protocols. Furthermore, we show that such constrained situations actually arise in important primitives for connecting logical and arithmetic circuits, such as modulus conversion and bit decomposition.

ACM Symposium on Applied Computing•Mar 23, 2026•0 citations

Enhancement of security in cloud computing with secure multi-party computation

Abhijeet Kumar, N J.V.Vineetha, P Sai Chakradar +1 more

The N sets of parties which are allowed by unconditionally the secure multiparty computation (MPC) for computing securely with a registered function f with the help of unbounded adversary computational at some specified field. Here one can corrupt t among n parties maliciously corrupt. The Protocols of MPC which are known and efficient are developed for online or offline framework. Coming to the offline process, the private & random multiplication-triples which is sharable can be generated by the parties in this framework. Later on, these are useful for online to evaluate the multiplication of gates securely in a circuit which describes as f. In this, Protocols of the MPC efficiency depends on the how the offline implementation efficiently. Here, we proposed a simple method, for shared & private multiplication-triples which are random in nature generation without any conditions securely & safely. The typical protocols face this issue, when the random values of shared pairs produced initially. And also, in computing the product values which is shared for every pair. After that, protocols of multiplication and values which are considered as communication intensive. In proposed scheme, the multiplication protocols are completely used in different manner. Later on, we observe that the share multiplication-triples verification by parties or they are extracted securely or not. With the use of setting of the hybrid network and asynchronous, linear communication MPC protocols used which are multiplication gate overhead & indicates as f. The above are the improvements on the typical MPC protocols with the help of hybrid networking setting, asynchronous and complexity of the communication, if we give to result of synchronous setting in our system. It results efficient MPC protocols which are rounded.

International Journal of Engineering & Technology•Dec 21, 2017•1 citation

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik +1 more

At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.

arXiv:2610.27609•Oct 20, 2026•0 citations
Performing L pairs of multiplication with known (k, n)-linear secret sharing-based n party multiplication protocols using an (offline) preprocessing by the Beaver multiplication triple requires 2Lk elements of on-line communications where k is the threshold. This paper proposes a simultaneous multiplication protocol for L pairs based on (k, L, n)-packed linear secret sharing. By embedding L secret information into each share using (k, L, n)-packed linear secret sharing, though partial information of secret information is leaked from k - l + 1 shares for 1 ≤ l ≤ L, the proposed protocol can perform L multiplications with 2k elements of online communications. As applications of the proposed simultaneous multiplication protocol, we also introduce a simultaneous comparison protocol and an improvement of the communication cost of Araki et al.'s n party group-wise maximum/minimum value aggregation protocol. For example, when computing the maximum/minimum value of eight 64-bit data, our proposed aggregation protocol can reduce 59.6% of the communication cost.
parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.
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.
The advantage of mixed-protocol multi-party secure computation frameworks lies in their ability to utilize different sharing types optimally for diverse tasks. A key module in these frameworks are Boolean-to-arithmetic secret sharing conversion protocols, which transfer a secret value from Boolean secret sharing to arithmetic secret sharing. This conversion process can either take in the Boolean secret sharing of a bit or a secret binary string. In this work, we suggest the application of an innovative correlated random tuple for this task in the semi-honest three-party (3PC) setting. This tuple provides the basis for building Boolean-to-arithmetic share conversion protocols. Specifically, we propose two such protocols in the semi-honest 3PC setting, the first protocol takes as input the Boolean secret sharing of a bit, and the second protocol takes as input the Boolean secret sharing of a secret binary string. When it comes to concrete efficiency, the first protocol shows superior performance compared to the existing state-of-the-art in ABY3 (CCS ’18). It achieves this by reducing the total required communication from 2ℓ bits per party to 4ℓ/3+1 bits (including 4ℓ/3 bits in the setup phase, and 1 bit in the online phase) per party, while maintaining a single round of optimized communication. On the other hand, the second protocol involves two rounds of online communication and its communication cost is comparable to that of ABY2.0 (USENIX’21) that relies on correlated oblivious transfer.
In the context of secret-sharing-based secure multiparty computation, multiplication is a fundamental operation. To date, multiplication protocols with reduced communication have been actively studied, and recent works have achieved one-round multiplication with each party sending only a single element. In this work, we propose a constrained multiplication protocol. While our protocol is applicable only in constrained situations, it reduces the total communication in practical applications to one third to one third of that of such protocols. Furthermore, we show that such constrained situations actually arise in important primitives for connecting logical and arithmetic circuits, such as modulus conversion and bit decomposition.
The N sets of parties which are allowed by unconditionally the secure multiparty computation (MPC) for computing securely with a registered function f with the help of unbounded adversary computational at some specified field. Here one can corrupt t among n parties maliciously corrupt. The Protocols of MPC which are known and efficient are developed for online or offline framework. Coming to the offline process, the private & random multiplication-triples which is sharable can be generated by the parties in this framework. Later on, these are useful for online to evaluate the multiplication of gates securely in a circuit which describes as f. In this, Protocols of the MPC efficiency depends on the how the offline implementation efficiently. Here, we proposed a simple method, for shared & private multiplication-triples which are random in nature generation without any conditions securely & safely. The typical protocols face this issue, when the random values of shared pairs produced initially. And also, in computing the product values which is shared for every pair. After that, protocols of multiplication and values which are considered as communication intensive. In proposed scheme, the multiplication protocols are completely used in different manner. Later on, we observe that the share multiplication-triples verification by parties or they are extracted securely or not. With the use of setting of the hybrid network and asynchronous, linear communication MPC protocols used which are multiplication gate overhead & indicates as f. The above are the improvements on the typical MPC protocols with the help of hybrid networking setting, asynchronous and complexity of the communication, if we give to result of synchronous setting in our system. It results efficient MPC protocols which are rounded.
At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.