International Association
for Cryptologic Research

The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits. In the random oracle model, we construct two garbling schemes: - The first scheme targets mixed circuits modulo some $N\approx 2^b$. Addition gates are free. Each multiplication gate costs $O(\lambda \cdot b^{1.5})$ communication. Each bit-decomposition costs $O(\lambda \cdot b^{2} / \log{b})$. - The second scheme targets mixed circuit modulo some $N\approx 2^b$. Each addition gate and multiplication gate costs $O(\lambda \cdot b \cdot \log b / \log \log b)$. Every bit-decomposition costs $O(\lambda \cdot b^2 / \log b)$. Our schemes improve on the work of Ball, Malkin, and Rosulek [CCS'16] in the same model. Additionally relying on the DCR assumption, we construct in the programmable random oracle model a more efficient garbling scheme targeting mixed circuits over $\mathbb Z_{2^b}$, where addition gates are free, and each multiplication or bit-decomposition gate costs $O(\lambda_{DCR} \cdot b)$ communication. We improve on the recent work of Ball, Li, Lin, and Liu [Eurocrypt'23] which also relies on the DCR assumption.

The beautiful work of Applebaum, Ishai, and Kushileviz [FOCS’11] initiated the study of arithmetic variants of Yao’s garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit C : Rn → Rm over a ring R into a garbled circuit \widehat{C} and n affine functions Li for i ∈ [n], such that \widehat{C} and Li(xi) reveals only the output C(x) and no other information of x. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting C into a Boolean circuit and applying Yao’s garbled circuit treat the inputs as bit strings instead of ring elements, and hence is not “arithmetic”. In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit |\widehat{C}| and that of the computation tableau |C|ℓ in the clear, where ℓ is the bit length of wire values (e.g., Yao’s garbled circuit has rate O(λ)). – We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz. – We construct an arithmetic garbling scheme for modular computation over R = Zp for any integer modulus p, based on either DCR or LWE. The DCR-based instantiation achieves rate O(λ) for large p. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget. – We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling were only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.

This paper introduces LERNA, a new framework for single-server secure aggregation. Our protocols are tailored to the setting where multiple consecutive aggregation phases are performed with the same set of clients, a fraction of which can drop out in some of the phases. We rely on an initial secret sharing setup among the clients which is generated once-and-for-all, and reused in all following aggregation phases. Compared to prior works [Bonawitz et al. CCS’17, Bell et al. CCS’20], the reusable setup eliminates one round of communication between the server and clients per aggregation—i.e., we need two rounds for semi-honest security (instead of three), and three rounds (instead of four) in the malicious model. Our approach also significantly reduces the server’s computational costs by only requiring the reconstruction of a single secret-shared value (per aggregation). Prior work required reconstructing a secret-shared value for each client involved in the computation. We provide instantiations of LERNA based on both the Decisional Composite Residuosity (DCR) and (Ring) Learning with Rounding ((R)LWR) assumptions respectively and evaluate a version based on the latter assumption. In addition to savings in round-complexity (which result in reduced latency), our experiments show that the server computational costs are reduced by two orders of magnitude in comparison to the state-of-the-art. In settings with a large number of clients, we also reduce the computational costs up to twenty-fold for most clients, while a small set of “heavy clients” is subject to a workload that is still smaller than that of prior work.

An important theme in the research on attribute-based encryption (ABE) is minimizing the sizes of secret keys and ciphertexts. In this work, we present two new ABE schemes with *constant-size* secret keys, i.e., the key size is independent of the sizes of policies or attributes and dependent only on the security parameter $\lambda$. - We construct the first key-policy ABE scheme for circuits with constant-size secret keys, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$, which concretely consist of only three group elements. The previous state-of-the-art scheme by [Boneh et al., Eurocrypt '14] has key size polynomial in the maximum depth $d$ of the policy circuits, ${|\mathsf{sk}_f|=\mathrm{poly}(d,\lambda)}$. Our new scheme removes this dependency of key size on $d$ while keeping the ciphertext size the same, which grows linearly in the attribute length and polynomially in the maximal depth, ${|\mathsf{ct}_{\mathbf{x}}|=|\mathbf{x}|\mathrm{poly}(d,\lambda)}$. - We present the first ciphertext-policy ABE scheme for Boolean formulae that simultaneously has constant-size keys and succinct ciphertexts of size independent of the policy formulae, namely, ${|\mathsf{sk}_f|=\mathrm{poly}(\lambda)}$ and ${|\mathsf{ct}_{\mathbf{x}}|=\mathrm{poly}(|\mathbf{x}|,\lambda)}$. Concretely, each secret key consists of only two group elements. Previous ciphertext-policy ABE schemes either have succinct ciphertexts but non-constant-size keys [Agrawal--Yamada, Eurocrypt '20, Agrawal--Wichs--Yamada, TCC '20], or constant-size keys but large ciphertexts that grow with the policy size as well as the attribute length. Our second construction is the first ABE scheme achieving *double succinctness*, where both keys and ciphertexts are smaller than the corresponding attributes and policies tied to them. Our constructions feature new ways of combining lattices with pairing groups for building ABE and are proven selectively secure based on LWE and in the generic (pairing) group model. We further show that when replacing the LWE assumption with its adaptive variant introduced in [Quach--Wee--Wichs FOCS '18], the constructions become adaptively secure.

In this work, we address communication, computation, and round efficiency of unconditionally secure multi-party computation for arithmetic circuits in the honest majority setting. We achieve both algorithmic and practical improvements: - The best known result in the semi-honest setting has been due to Damgard and Nielsen (CRYPTO 2007). Over the last decade, their construction has played an important role in the progress of efficient secure computation. However despite a number of follow-up works, any significant improvements to the basic semi-honest protocol have been hard to come by. We show 33% improvement in communication complexity of this protocol. We show how to generalize this result to the malicious setting, leading to the best known unconditional honest majority MPC with malicious security. - We focus on the round complexity of the Damgard and Nielsen protocol and improve it by a factor of 2. Our improvement relies on a novel observation relating to an interplay between Damgard and Nielsen multiplication and Beaver triple multiplication. An implementation of our constructions shows an execution run time improvement compared to the state of the art ranging from 30% to 50%.