A secret-shared shuffle (SSS) protocol permutes a secret-shared vector using a random secret permutation.It has found numerous applications, however, it is also an expensive operation and often a performance bottleneck.Chase et al. (Asiacrypt'20) recently proposed a highly efficient semi-honest two-party SSS protocol known as the CGP protocol.It utilizes purposely designed pseudorandom correlations that facilitate a communication-efficient online shuffle phase.That said, semihonest security is insufficient in many real-world application scenarios since shuffle is usually used for highly sensitive applications.Considering this, recent works (CANS'21, NDSS'22) attempted to enhance the CGP protocol with malicious security over authenticated secret sharings.However, we find that these attempts are flawed, and malicious adversaries can still learn private information via malicious deviations.This is demonstrated with concrete attacks proposed in this paper.Then the question is how to fill the gap and design a maliciously secure CGP shuffle protocol.We answer this question by introducing a set of lightweight correlation checks and a leakage reduction mechanism.Then we apply our techniques with authenticated secret sharings to achieve malicious security.Notably, our protocol, while increasing security, is also efficient.In the two-party setting, experiment results show that our maliciously secure protocol introduces an acceptable overhead compared to its semi-honest version and is more efficient than the state-of-the-art maliciously secure SSS protocol from the MP-SPDZ library.
A secret-shared shuffle (SSS) protocol permutes a secret-shared vector using a random secret permutation.It has found numerous applications, however, it is also an expensive operation and often a performance bottleneck.Chase et al. (Asiacrypt'20) recently proposed a highly efficient semi-honest two-party SSS protocol known as the CGP protocol.It utilizes purposely designed pseudorandom correlations that facilitate a communication-efficient online shuffle phase.That said, semihonest security is insufficient in many real-world application scenarios since shuffle is usually used for highly sensitive applications.Considering this, recent works (CANS'21, NDSS'22) attempted to enhance the CGP protocol with malicious security over authenticated secret sharings.However, we find that these attempts are flawed, and malicious adversaries can still learn private information via malicious deviations.This is demonstrated with concrete attacks proposed in this paper.Then the question is how to fill the gap and design a maliciously secure CGP shuffle protocol.We answer this question by introducing a set of lightweight correlation checks and a leakage reduction mechanism.Then we apply our techniques with authenticated secret sharings to achieve malicious security.Notably, our protocol, while increasing security, is also efficient.In the two-party setting, experiment results show that our maliciously secure protocol introduces an acceptable overhead compared to its semi-honest version and is more efficient than the state-of-the-art maliciously secure SSS protocol from the MP-SPDZ library.
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 revisit shuffle protocols for Shamir secret sharing. Existing constructions either produce non-uniform shuffles or incur high communication and round complexity, sometimes exponential in the number of parties. We propose two new shuffle protocols that achieve uniform shuffling with communication complexity O ( k + l log k n 2 m log m ) for an m × l matrix shared among n parties, where k ≤ m is a tunable parameter. The first protocol is concretely efficient, while the second achieves the best-known O ( n m l ) online communication and O ( n ) rounds. Experiments show significant improvements in online efficiency and total cost over prior work. Our key technical ingredient is a novel permutation sharing technique that represents permutations via smaller permutation matrices, making their application significantly more efficient. The first protocol applies independent secret permutations sequentially, while the second builds on shuffle correlation to achieve optimal online complexity. We further extend shuffle correlation to support guaranteed output delivery with linear online communication, yielding SLIDE (shuffle Shamir secret shares uniformly with linear online communication and guaranteed output delivery), the first protocol achieving both O ( n m l ) online communication and guaranteed output delivery. Our constructions rely only on basic Shamir secret sharing over any field F with | F | > n . As shuffling is a fundamental primitive for multiparty computation tasks such as sorting and oblivious data structures, our results enable more efficient and scalable secure computation in practice.
Secure multiparty computation enables a set of parties to securely carry out a joint computation of their private inputs without revealing anything but the output. In the past few years, the efficiency of secure computation protocols has increased in leaps and bounds. However, when considering the case of security in the presence of malicious adversaries (who may arbitrarily deviate from the protocol specification), we are still very far from achieving high efficiency. In this paper, we consider the specific case of three parties and an honest majority. We provide general techniques for improving efficiency of cut-and-choose protocols on multiplication triples and utilize them to significantly improve the recently published protocol of Furukawa et al. (ePrint 2016/944). We reduce the bandwidth of their protocol down from 10 bits per AND gate to 7 bits per AND gate, and show how to improve some computationally expensive parts of their protocol. Most notably, we design cache-efficient shuffling techniques for implementing cut-and-choose without randomly permuting large arrays (which is very slow due to continual cache misses). We provide a combinatorial analysis of our techniques, bounding the cheating probability of the adversary. Our implementation achieves a rate of approximately 1.15 billion AND gates per second on a cluster of three 20-core machines with a 10Gbps network. Thus, we can securely compute 212,000 AES encryptions per second (which is hundreds of times faster than previous work for this setting). Our results demonstrate that high-throughput secure computation for malicious adversaries is possible.
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 this work we formalize the notion of a two-party permutation correlation (A,B),(C,π) s.t. π(A)=B+C for a random permutation π of n elements and vectors A,B,C∈Fn . This correlation can be viewed as an abstraction and generalization of the Chase et al. (Asiacrypt 2020) share translation protocol. We give a systematization of knowledge for how such a permutation correlation can be derandomized to allow the parties to perform a wide range of oblivious permutations of secret-shared data. This systematization immediately enables the translation of various popular honest-majority protocols to be efficiently instantiated in the two-party setting, e.g. collaborative filtering, sorting, database joins, graph algorithms, and many more. We give two novel protocols for efficiently generating a random permutation correlation. The first uses MPC-friendly PRFs to generate a correlation of n elements, each of size ℓ=log∣F∣ bits, with O(nℓ) bit-OTs, time, communication, and only 3 rounds including setup. Similar asymptotics previously required relatively expensive public-key cryptography, e.g. Paillier or LWE. Our protocol implementation for n=220,ℓ=128 requires just 7 s & ∼2ℓn bits of communication, a respective 40 & 1.1× improvement on the LWE solution of Juvekar at al. (CCS 2018). The second protocol is based on pseudo-random correlation generators and achieves an overhead that is sublinear in the string length ℓ , i.e. the communication and number of OTs is O(nlogℓ) . The overhead of the latter protocol has larger hidden constants, and therefore is more efficient only when long strings are permuted, e.g. in graph algorithms. Finally, we present a suite of highly efficient protocols based on permutations for performing various batched random access operations. These include the ability to extract a hidden subset of a secret-shared list. More generally, we give ORAM-like protocols for obliviously reading and writing from a list in a batched manner. We argue that this suite of batched random access protocols should be a first class primitive in the MPC practitioner’s toolbox.(The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/ .)
Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party's input. Correctness of the honest party's output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some heuristic enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.