International Association
for Cryptologic Research

Garbled circuits, introduced in the seminal work of Yao (FOCS, 1986), have received considerable attention in the boolean setting due to their efficiency and application to round-efficient secure computation. In contrast, arithmetic garbling schemes have received much less scrutiny. The main efficiency measure of garbling schemes is their rate, defined as the bit size of each gate's output divided by the (amortized) garbled gate. Despite recent progress, state-of-the-art garbling schemes for arithmetic circuits suffer from important limitations: all existing schemes are either restricted to B-bounded integer arithmetic circuits (a computational model where the arithmetic is performed over Z and correctness is only guaranteed if no intermediate computation exceeds the bound B) and achieve constant rate only for very large bounds B = 2^Ω(λ^3), or have rate at most O(1/λ) otherwise, where λ denotes a security parameter. In this work, we improve this state of affairs in both settings. - As our main contribution, we introduce the first arithmetic garbling scheme over modular rings Z_B with rate O(log λ / λ), breaking for the first time the 1/λ-rate barrier for modular arithmetic garbling. Our construction relies on the power-DDH assumption. - As a secondary contribution, we introduce a new arithmetic garbling scheme for B-bounded integer arithmetic that achieves a constant rate for bounds B as low as 2^O(λ). Our construction relies on a new non-standard KDM-security assumption on Paillier encryption with small exponents.

We introduce improved constructions of trapdoor hash (TDH) schemes under either DDH or DCR. Compared with the original construction of (Döttling et al., Crypto 2019), our new schemes are more expressive and feature more compact encoding keys. Expressivity: Our TDH scheme allows computing arbitrary functions of the form f(x,y) = ∑ᵢf_i(x) . g_i(y), where f_i, g_i are logarithmic-depth functions. This improves over the original construction that was restricted to computing the inner product between x and y. Compactness: Our TDH scheme has encoding keys of length |y|.(1+o(1)), shaving an Ω(λ) factor compared to the original construction. Equipped with our new scheme, we revisit numerous applications of TDH and construct various low-communication cryptographic primitives that improve over the state of the art, including: - Rate-1 batch OT with semi-honest statistical sender privacy from DDH. Previously, it was only known under DDH+LPN (even without semi-honest statistical sender privacy). As a consequence of our rate-1 batch OT, we also obtain rate-1 lossy trapdoor functions with public keys of size o(n) from DDH. - Optimal preprocessing PIR from DCR, where after a single broadcast of o(n) bits, a server with a size-n database and a client can execute any number of PIR queries adaptively with fully optimal communication (upload communication exactly log(n), download communication exactly 1). Previously, such communication features were not known, even under strong cryptographic assumptions. - Rate-1/2 PSI and fuzzy PSI from DCR, where after a single broadcast of o(n) bits, a server with a size-n database and a client can execute any number of (fuzzy) membership queries with upload and download communication exactly log(n). Previously, such communication features were not known, even under strong cryptographic assumptions. - Secure 2-party computation of layered circuit with one-sided statistical security and communication sublinear in both the circuit size and the largest input, from DCR. Previously, similar results were only known from FHE.

Homomorphic secret sharing (HSS) is a distributed analogue of fully homomorphic encryption (FHE) where following an input-sharing phase, two or more parties can locally compute a function over their private inputs to obtain shares of the function output. Over the last decade, HSS schemes have been constructed from an array of different assumptions. However, all existing HSS schemes, except ones based on assumptions known to imply multi-key FHE, require a public-key infrastructure (PKI) or a correlated setup between parties. This limitation carries over to many applications of HSS. In this work, we construct *multi-key* homomorphic secret sharing (MKHSS), where given only a common reference string (CRS), two parties can secret share their inputs to each other and then perform local computations as in HSS, eliminating the need for PKI or a correlated setup. Specifically, we present the first MKHSS schemes supporting all NC1 computations from either the decisional Diffie--Hellman (DDH) assumption, the decisional composite residuosity (DCR) assumption, or DDH-like assumptions in class group. Our constructions imply the following applications in the CRS model: - Succinct two-round secure computation. Under the same assumptions as our MKHSS schemes, we construct a succinct, two-round, two-party secure computation protocol for NC1 circuits. Previously, such a result was only known from the learning with errors assumption. - Attribute-based NIKE. Under DCR or class group assumptions, we construct non-interactive key exchange (NIKE) protocols where two parties agree on a key if and only if their secret attributes satisfy a public NC1 predicate. This significantly generalizes the existing notion of password-based NIKE. - Public-key PCFs. Under DCR or class group assumptions, we construct public-key pseudorandom correlation functions (PCFs) for any NC1 correlation. This yields the first public-key PCFs for Beaver triples (and more) from non-lattice assumptions. - Silent MPC. Under DCR or class group assumptions, we construct a p-party secure computation protocol in the silent preprocessing model where the preprocessing phase has communication O(p), ignoring polynomial factors. All prior protocols that do not rely on multi-key FHE techniques require ω(p²) communication.

A homomorphic secret sharing (HSS) scheme allows a client to delegate a computation to a group of untrusted servers while achieving input privacy as long as at least one server is honest. In recent years, many HSS schemes have been constructed that have, in turn, found numerous applications to cryptography. Prior work on HSS focuses on the setting where the servers are semi-honest. In this work we lift HSS to the setting of malicious evaluators. We propose the notion of *HSS with verifiable evaluation* (ve-HSS) that guarantees correctness of output *even when all the servers are corrupted*. ve-HSS retains all the attractive features of HSS and adds the new feature of succinct (public) verification of output. We present *black-box* constructions of ve-HSS by devising generic transformations for semi-honest HSS schemes (with negligible error). This provides a new non-interactive method for verifiable and private outsourcing of computation.

We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of single ``active'' branch. Crucially, the identity of the active branch must remain hidden from the protocol participants. While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO'20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving {\em more than two parties}. In this work, we provide a generic framework for branching multi-party computation that supports {\em any number of parties}. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.

In the classical notion of multiparty computation (MPC), an honest party learning private inputs of others, either as a part of protocol specification or due to a malicious party's unspecified messages, is not considered a potential breach. Several works in the literature exploit this seemingly minor loophole to achieve the strongest security of guaranteed output delivery via a trusted third party, which nullifies the purpose of MPC. Alon et al. (CRYPTO 2020) presented the notion of {\it Friends and Foes} ($\mathtt{FaF}$) security, which accounts for such undesired leakage towards honest parties by modelling them as semi-honest (friends) who do not collude with malicious parties (foes). With real-world applications in mind, it's more realistic to assume parties are semi-honest rather than completely honest, hence it is imperative to design efficient protocols conforming to the $\mathtt{FaF}$ security model. Our contributions are not only motivated by the practical viewpoint, but also consider the theoretical aspects of $\mathtt{FaF}$ security. We prove the necessity of semi-honest oblivious transfer for $\mathtt{FaF}$-secure protocols with optimal resiliency. On the practical side, we present QuadSquad, a ring-based 4PC protocol, which achieves fairness and GOD in the $\mathtt{FaF}$ model, with an optimal corruption of $1$ malicious and $1$ semi-honest party. QuadSquad is, to the best of our knowledge, the first practically efficient $\mathtt{FaF}$ secure protocol with optimal resiliency. Its performance is comparable to the state-of-the-art dishonest majority protocols while improving the security guarantee from abort to fairness and GOD. Further, QuadSquad elevates the security by tackling a stronger adversarial model over the state-of-the-art honest-majority protocols, while offering a comparable performance for the input-dependent computation. We corroborate these claims by benchmarking the performance of QuadSquad. We also consider the application of liquidity matching that deals with highly sensitive financial transaction data, where $\mathtt{FaF}$ security is apt. We design a range of $\mathtt{FaF}$ secure building blocks to securely realize liquidity matching as well as other popular applications such as privacy-preserving machine learning (PPML). Inclusion of these blocks makes QuadSquad a comprehensive framework.