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.

Garbling schemes are a fundamental cryptographic tool for enabling private computations and ensuring that nothing leaks beyond the output. As a widely studied primitive, significant efforts have been made to reduce their size. Until recently, all such schemes followed the Lindell and Pinkas paradigm for Boolean circuits (JoC 2009), where each gate is represented as a set of ciphertexts computed using only symmetric-key primitives. However, this approach is inherently limited to O(λ) bits per gate, where λ is the security parameter. Recently, it has been shown that achieving smaller garbled circuit size is possible under stronger assumptions, such as variants of Learning with Errors (LWE) or Indistinguishability Obfuscation (iO). In addition to requiring high-end cryptography, none of these constructions is black-box in the underlying cryptographic primitives, a key advantage of prior work. In this paper, we present the first approach to garbling Boolean circuits that makes a black-box use of a group and uses o(λ) bits per gate. Building on a novel application of the Reverse Multiplication-Friendly Embeddings (RMFE) paradigm (Cascudo et al., CRYPTO 2018), we introduce a new packing mechanism for garbling schemes. Our results introduce two new succinct schemes that achieve improved rates by a factor of √log(λ), retaining the black-box usage. (1) Our first scheme is proven in the Generic Group model (GGM) for circuits with Ω(√log(λ)) width, obtaining a garbled circuit size of λ . |C| / √log(λ). (2) Our second scheme is proven in the plain model under the Power-DDH assumption, attaining a garbled circuit size of λ . |C| / √log(λ) + poly(λ) . |C| . depth(C), but is restricted to layered circuits. **Our schemes are the first to achieve sublinear (in λ) cost per gate under assumptions that do not imply fully homomorphic encryption**; in addition, our scheme is also the first to achieve this while making a black-box use of cryptography.

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols, in particular, when communication can be sublinear in the circuit representation size of the desired function. While several techniques have demonstrated the viability of sublinear secure computation in the two-party setting, known methods for the corresponding multi-party setting rely either on fully homomorphic encryption, non-standard hardness assumptions, or are limited to a small number of parties. In this work, we expand the study of multi-party sublinear secure computation by demonstrating sublinear-communication 10-party computation from various combinations of standard hardness assumptions. In particular, our contributions show: - 8-party homomorphic secret sharing under the hardness of (DDH or DCR), the superpolynomial hardness of LPN, and the existence of constant-depth pseudorandom generators; - A general framework for achieving (N+2)-party sublinear secure computation assuming N-party homomorphic secret sharing. Together, our constructions imply the existence of a 10-party MPC protocol with sublinear computation. At the core of our techniques lies a novel series of computational approaches based homomorphic secret sharing.