It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). It enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication. Much research has gone into making each protocol (equality testing, interval testing, etc.) more efficient. In this work, we make a set of multiple protocols more efficient by transforming them into their equivalent batch processing form and propose two protocols: “Batch Logical OR” and “Batch Logical AND.” Using proposed protocols recursively, we also propose “Batch Logical OR-AND” and “Batch Logical AND-OR,” and show arbitrary formula consisting of Boolean protocols, OR gates, and AND gates can be batched. Existing logical OR and logical AND protocols consisting of t equality testing invocations have a communication complexity of O(lt), where l is the bit length of the secrets. Our batched versions of these protocols reduce it to O(l+t). For t interval testing invocations, they reduce both communication and round complexity. Thus they can make the queries on a secret shared database more efficient. For example, the use of the proposed protocols reduces the communication complexity for a query consisting of equality testing and interval testing by approximately 70% compared to the use of the corresponding existing protocols. The concept of the proposed protocols is versatile and can be applied to logical formulae consisting of protocols other than equality testing and interval testing, thereby making them more efficient as well.
It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). It enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication. Much research has gone into making each protocol (equality testing, interval testing, etc.) more efficient. In this work, we make a set of multiple protocols more efficient by transforming them into their equivalent batch processing form and propose two protocols: “Batch Logical OR” and “Batch Logical AND.” Using proposed protocols recursively, we also propose “Batch Logical OR-AND” and “Batch Logical AND-OR,” and show arbitrary formula consisting of Boolean protocols, OR gates, and AND gates can be batched. Existing logical OR and logical AND protocols consisting of t equality testing invocations have a communication complexity of O(lt), where l is the bit length of the secrets. Our batched versions of these protocols reduce it to O(l+t). For t interval testing invocations, they reduce both communication and round complexity. Thus they can make the queries on a secret shared database more efficient. For example, the use of the proposed protocols reduces the communication complexity for a query consisting of equality testing and interval testing by approximately 70% compared to the use of the corresponding existing protocols. The concept of the proposed protocols is versatile and can be applied to logical formulae consisting of protocols other than equality testing and interval testing, thereby making them more efficient as well.
It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). However, one of the biggest problems with MPC is that it requires a vast amount of communication. We analyzed existing MPC protocols and found that the random number bitwise-sharing protocol used by many of them is notably inefficient. By devising a representation of the truth values and using special form prime numbers, we propose efficient random number bitwise-sharing protocols, dubbed “Extended-Range I and II,” which reduce the communication complexity to approximately 1/6th that of the best of the existing such protocol. We reduced the communication complexity to approximately 1/26th by reducing the abort probability, thereby making previously necessary backup computation unnecessary. Using our improved protocol, “Lightweight Extended-Range II,” we reduced the communication complexities of equality testing, comparison, interval testing, and bit-decomposition, all of which use the random number bitwise-sharing protocol, by approximately 91, 79, 67, and 23% (for 32-bit data), respectively. We also reduce the communication complexity of private exponentiation by about 70% (for 32-bit data and five 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% 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.
We propose constant-round protocols for interval tests, equality tests, and comparisons where shared secret inputs are not given bitwise. In [9]. Damgard et al. presented a novel protocol called the bit-decomposition, which can convert a polynomial sharing of an element in prime field p into sharings of bits. Though, by using the bit-decomposition protocol, those protocols can be constructed with constant round complexities theoretically, it involves expensive computation, leading to relatively high round and communication complexities. In this paper, we construct more efficient protocols for those protocols without relying on the bit-decomposition protocol. In the interval test protocol, checking whether a shared secret exists in the known interval is reduced to checking whether a bitwise-shared random secret exists in the appropriate interval. In the comparison protocol, comparing two shared secrets is reduced to comparing the two secrets via p/2 indirectly where p is an odd prime for an underlying linear secret sharing scheme. In the equality test protocol, checking whether two shared secrets are equal is reduced to checking whether the difference of the two secrets is zero and furthermore checking whether the difference is a zero is reduced to checking quadratice residuosity of a random secret in a probabilistic way.
Secure multi-party computation (MPC) is a cryptographic tool that enables a set of parties to compute a function jointly while keeping each input secret. Since MPC based on secret sharing (SS) achieves high throughput and works fast, many applications have been developed. However, SS-based MPC requires many communication rounds in general, and this becomes a performance bottleneck in real-world applications under high-latency networks. In this paper, we propose SS-based secure three-party computation with almost no preprocessing based on our new (small-)constant-round fundamental gates, by revisiting a framework in a few previous works where a number of parties are assisted by another party who may partially learn secret information. Instead of ordinary logical gates, our fundamental gate is an efficient Equality, for which the result leaks to the third party, and we develop novel two-round constructions of secure building-block protocols (LessThan Comparison, RightShift, Table LookUp, etc.) from the insecure Equality. To show the practicality of our protocols, we implement a secure exact edit distance protocol for two genome strings. Our experiments show that in some network setting our protocol is about 2 times faster (14 times faster taking preprocessing into consideration) than the state-of-the-art SS-based protocol (Ohata and Nuida, FC 2020).
Bit-decomposition is an important primitive in multi-party computation (MPC). Given a sharing of secret x, it allows the parties to compute the sharings of the bits of x in constant rounds. With the help of bit-decomposition, we will be able to construct constant-rounds protocols for various MPC problems, such as equality test, comparison, public modulo reduction and private exponentiation, which are four main applications of bit-decomposition. However, when considering perfect security, bit-decomposition does not have a linear communication complexity. Thus any protocols involving bit-decomposition inherit this inefficiency, i.e. the communication complexity is non-linear. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfect secure protocols with linear communication complexity. It is already proved that equality test, comparison and public modulo reduction can be solved without involving bit-decomposition and the communication complexity can be reduced to linear. However, it remains an open problem whether private exponentiation could be done without relying on bit-decomposition. In this paper, maybe somewhat surprisingly, we show that it can. That is to say, we construct
Abstract. As an extension of multi-party computation (MPC), we propose the concept of secure parallel multi-party computation which is to securely compute multi-functions against an adversary with multistructures. Precisely, there are m functions f1,..., fm and m adversary structures A1,..., Am, where fi is required to be securely computed against an Ai-adversary. We give a general construction to build a parallel multi-party computation protocol from any linear multi-secret sharing scheme (LMSSS), provided that the access structures of the LMSSS allow MPC at all. When computing complicated functions, our protocol has more advantage in communication complexity than the “direct sum” method which actually executes a MPC protocol for each function. The paper also provides an efficient and generic construction to obtain from any LMSSS a multiplicative LMSSS for the same multi-access structure. 1