In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data set. Our protocols capture various applications such as oblivious shuffles, circular shifts, matrix multiplications, to name just a few. A notable feature enjoyed by our protocols, is that they admit a round-optimal (more precisely, one-round) online computation phase, once an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal online phase. The most efficient instantiations of our protocols are obtained in the so-called client-aided client-server setting, where the offline phase is run by a semi-honest input party (client) who will then distribute the generated correlated randomness to the computing parties (servers). When comparing the total running time to the previous best two-party oblivious shuffle protocol by Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided setting is up to 105 times and 152 times faster, in the LAN and WAN setting, respectively. We additionally show how the Chase et al. protocol (which is a standard two-party protocol) can be modified to leverage the advantages of the client-aided setting, but show that, even doing so, our scheme is still two times faster in the online phase and 1.34 times faster in total on average.
In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data set. Our protocols capture various applications such as oblivious shuffles, circular shifts, matrix multiplications, to name just a few. A notable feature enjoyed by our protocols, is that they admit a round-optimal (more precisely, one-round) online computation phase, once an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal online phase. The most efficient instantiations of our protocols are obtained in the so-called client-aided client-server setting, where the offline phase is run by a semi-honest input party (client) who will then distribute the generated correlated randomness to the computing parties (servers). When comparing the total running time to the previous best two-party oblivious shuffle protocol by Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided setting is up to 105 times and 152 times faster, in the LAN and WAN setting, respectively. We additionally show how the Chase et al. protocol (which is a standard two-party protocol) can be modified to leverage the advantages of the client-aided setting, but show that, even doing so, our scheme is still two times faster in the online phase and 1.34 times faster in total on average.
In this work, we consider the problem of secure multi-party computation (MPC) with n parties where at most t are under the control of a computationally bounded adversary given the constraint t < n/2. We aim to design a round efficient protocol by minimizing the number of rounds in which the broadcast primitive is involved. In this setting, the previous best protocol can be attributed to Katz-Koo (EUROCRYPT 2007) which is set in the offline-online paradigm (where the parties generate preprocessing data during the offline phase to lighten the computation in the online phase). Their online phase is a constant round protocol with no invocations of broadcast, while the offline phase protocol needs total 29 rounds with a broadcast invocation in one round. Our work improves the round complexity of their offline phase protocol, by running in 4 rounds, with only a single broadcast round. Additionally, we also improve the communication complexity of the offline phase protocol by a factor of Ω(n3). As a technical contribution, we present the first two round computationally-secure verifiable secret-sharing (VSS) scheme that invokes broadcast in only one round.
We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base'' oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds. Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.
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/ .)
We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base" oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions:-Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semihonest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature.-Malicious security. We provide security against malicious parties (in the random oracle model) without additional interaction and with only a modest concrete overhead; prior to our work, no similar protocols were known with any number of rounds.-Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.
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.
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.