International Association for Cryptologic Research

International Association
for Cryptologic Research


Eduardo Soria-Vazquez


Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled Circuits 📺
Whilst secure multiparty computation (MPC) based on garbled circuits is concretely efficient for a small number of parties $n$, the gap between the complexity of practical protocols, which is $O(n^2)$ per party, and the theoretical complexity, which is $O(n)$ per party, is prohibitive for large values of $n$. In order to bridge this gap, Ben-Efraim, Lindell and Omri (ASIACRYPT 2017) introduced a garbled-circuit-based MPC protocol with an almost-practical pre-processing, yielding $O(n)$ complexity per party. However, this protocol is only passively secure and does not support the free-XOR technique by Kolesnikov and Schneider (ICALP 2008), on which almost all practical garbled-circuit-based protocols rely on for their efficiency. In this work, to further bridge the gap between theory and practice, we present a new $n$-party garbling technique based on a new variant of standard LPN-based encryption. Using this approach we can describe two new garbled-circuit based protocols, which have practical evaluation phases. Both protocols are in the preprocessing model, have $O(n)$ complexity per party, are actively secure and support the free-XOR technique. The first protocol tolerates full threshold corruption and ensures the garbled circuit contains no adversarially introduced errors, using a rather expensive garbling phase. The second protocol assumes that at least $n/c$ of the parties are honest (for an arbitrary fixed value $c$) and allows a significantly lighter preprocessing, at the cost of a small sacrifice in online efficiency. We demonstrate the practicality of our approach with an implementation of the evaluation phase using different circuits. We show that like the passively-secure protocol of Ben-Efraim, Lindell and Omri, our approach starts to improve upon other practical protocols with $O(n^2)$ complexity when the number of parties is around $100$.
Efficient Information-Theoretic Multi-Party Computation over Non-Commutative Rings 📺
Daniel Escudero Eduardo Soria-Vazquez
We construct the first efficient MPC protocol that only requires black-box access to a non-commutative ring $R$. Previous results in the same setting were efficient only either for a constant number of corruptions or when computing branching programs and formulas. Our techniques are based on a generalization of Shamir's secret sharing to non-commutative rings, which we derive from the work on Reed Solomon codes by Quintin, Barbier and Chabot (\textit{IEEE Transactions on Information Theory, 2013}). When the center of the ring contains a set $A = \{\alpha_0, \ldots, \alpha_n\}$ such that $\forall i \neq j, \alpha_i - \alpha_j \in R^*$, the resulting secret sharing scheme is strongly multiplicative and we can generalize existing constructions over finite fields without much trouble. Most of our work is devoted to the case where the elements of $A$ do not commute with all of $R$, but they just commute with each other. For such rings, the secret sharing scheme cannot be linear ``on both sides" and furthermore it is not multiplicative. Nevertheless, we are still able to build MPC protocols with a concretely efficient online phase and black-box access to $R$. As an example we consider the ring $\mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z})$, for which when $m > \log(n+1)$, \enote{maybe adapt/simplify the following claim as the comparison requires some nuances} we obtain protocols that require around $\lceil\log(n+1)\rceil/2$ less communication and $2\lceil\log(n+1)\rceil$ less computation than the state of the art protocol based on Circuit Amortization Friendly Encodings (Dalskov, Lee and Soria-Vazquez, \textit{ASIACRYPT 2020}). In this setting with a ``less commutative" $A$, our black-box preprocessing phase has a less practical complexity of $\poly(n)$. Due to this, we additionally provide specialized, concretely efficient preprocessing protocols for $R = \mathcal{M}_{m\times m}(\mathbb{Z}/2^k\mathbb{Z})$ that exploit the structure of the matrix ring.
Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability 📺
Recent years have seen a tremendous growth in the interest in se- cure multiparty computation (MPC) and its applications. While much progress has been made concerning its efficiency, many current, state-of-the-art protocols are vulnerable to Denial of Service attacks, where a cheating party may prevent the honest parties from learning the output of the computation, whilst remaining anonymous. The security model of identifiable abort aims to prevent these at- tacks, by allowing honest parties to agree upon the identity of a cheating party, who can then be excluded in the future. Several existing MPC protocols offer security with identifiable abort against a dishonest majority of corrupted parties. However, all of these protocols have a round complexity that scales linearly with the depth of the circuit (and are therefore unsuitable for use in high latency net- works) or use cryptographic primitives or techniques that have a high computa- tional overhead. In this work, we present the first efficient MPC protocols with identifiable abort in the dishonest majority setting, which run in a constant number of rounds and make only black-box use of cryptographic primitives. Our main construction is built from highly efficient primitives in a careful way to achieve identifiability at a low cost. In particular, we avoid the use of public-key operations outside of a setup phase, incurring a relatively low overhead on top of the fastest currently known constant-round MPC protocols based on garbled circuits. Our construction also avoids the use of adaptively secure primitives and heavy zero-knowledge machinery, which was inherent in previous works. In addition, we show how to upgrade our protocol to achieve public verifiability using a public bulletin board, allowing any external party to verify correctness of the computation or identify a cheating party.
Circuit Amortization Friendly Encodings and their Application to Statistically Secure Multiparty Computation 📺
Anders Dalskov Eysa Lee Eduardo Soria-Vazquez
At CRYPTO 2018, Cascudo et al. introduced Reverse Multiplication Friendly Embeddings (RMFEs). These are a mechanism to compute $\delta$ parallel evaluations of the same arithmetic circuit over a field $\mathbb{F}_q$ at the cost of a single evaluation of that circuit in $\mathbb{F}_{q^d}$, where $\delta < d$. Due to this inequality, RMFEs are a useful tool when protocols require to work over $\mathbb{F}_{q^d}$ but one is only interested in computing over $\mathbb{F}_q$. In this work we introduce Circuit Amortization Friendly Encodings (CAFEs), which generalize RMFEs while having concrete efficiency in mind. For a Galois Ring $R = GR(2^k,d)$, CAFEs allow to compute certain circuits over $\mathbb{Z}_{2^k}}$ at the cost of a single secure multiplication in $R$. We present three CAFE instantiations, which we apply to the protocol for MPC over $\mathbb{Z}_{2^k}}$ via Galois Rings by Abspoel et al. (TCC 2019). Our protocols allow for efficient switching between the different CAFEs, as well as between computation over $GR(2^k,d)$ and $\mathbb{F}_{2^{d}}$ in a way that preserves the CAFE in both rings. This adaptability leads to efficiency gains for e.g. Machine Learning applications, which can be represented as highly parallel circuits over $\mathbb{Z}_{2^k}}$ followed by bit-wise operations. From an implementation of our techniques, we estimate that an SVM can be evaluated on 250 images in parallel up to $\times 7$ as efficient using our techniques, compared to using the protocols from Abspoel et al. (TCC 2019).
Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
Carmit Hazay Peter Scholl Eduardo Soria-Vazquez
In this work, we present two new actively secure, constant-round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round complexity in the depth of the circuit, and compile it into a constant-round protocol based on garbled circuits, with very low overhead. 1. Our first protocol takes a generic approach using any secret-sharing-based MPC protocol for binary circuits, and a correlated oblivious transfer functionality. 2. Our second protocol builds on secret-sharing-based MPC with information-theoretic MACs. This approach is less flexible, being based on a specific form of MPC, but requires no additional oblivious transfers to compute the garbled circuit. In both approaches, the underlying secret-sharing-based protocol is only used for one actively secure $$\mathbb {F}_2$$ F 2 multiplication per AND gate . An interesting consequence of this is that, with current techniques, constant-round MPC for binary circuits is not much more expensive than practical, non-constant-round protocols. We demonstrate the practicality of our second protocol with an implementation and perform experiments with up to 9 parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous protocols in this setting by 60 times.
TinyKeys: A New Approach to Efficient Multi-Party Computation 📺
We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols does not depend on the number of honest parties, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for $$n-1$$ n-1 corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties’ keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption.We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around $$n=20$$ n=20 parties with $$h=6$$ h=6 honest parties, and as these increase we obtain up to a 13 times reduction (for $$n=400, h=120$$ n=400,h=120) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.
Concretely Efficient Large-Scale MPC with Active Security (or, TinyKeys for TinyOT)
In this work we develop a new theory for concretely efficient, large-scale MPC with active security. Current practical techniques are mostly in the strong setting of all-but-one corruptions, which leads to protocols that scale badly with the number of parties. To work around this issue, we consider a large-scale scenario where a small minority out of many parties is honest and design scalable, more efficient MPC protocols for this setting. Our results are achieved by introducing new techniques for information-theoretic MACs with short keys and extending the work of Hazay et al. (CRYPTO 2018), which developed new passively secure MPC protocols in the same context. We further demonstrate the usefulness of this theory in practice by analyzing the concrete communication overhead of our protocols, which improve upon the most efficient previous works.