International Association
for Cryptologic Research

We revisit the question of the overhead to achieve full security (i.e., guaranteed output delivery) in secure multiparty computation (MPC). Recent works have closed the gap between full security and semi-honest security, by introducing protocols where the parties first compute the circuit using a semi-honest protocol and then run a verification step with sublinear communication in the circuit size. However, the number of interaction rounds in the verification step is also sublinear in the circuit's size. Unlike communication, the round complexity typically grows with the circuit's \textit{depth} and not its size. Hence, for large but shallow circuits, this may yield a significant overhead. Motivated by this gap, we make the following contributions: (1) We present a new MPC framework to obtain full security, compatible with effectively \emph{any} ring, that has an additive communication overhead of only $O(\log |C|)$, where $|C|$ is the number of multiplication gates in the circuit, and a \textit{constant} number of additional rounds beyond the underlying semi-honest protocol. Our framework works with any linear secret sharing scheme and relies on a new to utilize the machinery of \textit{zero-knowledge fully linear interactive oracle proofs} (zk-FLIOP) in a black-box way. We present several instantiations to the building blocks of our compiler, from which we derive concretely efficient protocols in different settings. (2) We present extensions to the zk-FLIOP primitive for very general settings: one for proving statements over potentially non-commutative rings that only require certain commutative properties of its largest exceptional set; and one for proving statements over Galois Rings. For Galois rings, we present concrete improvements on the current state-of-the-art for the case of constant-round proofs, by making use of \emph{Reverse Multiplication Friendly Embeddings} (RMFEs).

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).