Welcome to the resource topic for 2025/1053
Title:
Breaking the 1/λ-Rate Barrier for Arithmetic Garbling
Authors: Geoffroy Couteau, Carmit Hazay, Aditya Hegde, Naman Kumar
Abstract: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 size of 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 \mathbb{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^{\Omega(\lambda^3)}, or have a rate at most O(1/\lambda) otherwise, where \lambda 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 \mathbb{Z}_B with rate O(\log\lambda/\lambda), breaking for the first time the 1/\lambda-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(\lambda)}. Our construction relies on a new non-standard KDM-security assumption on Paillier encryption with small exponents.
ePrint: https://eprint.iacr.org/2025/1053
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .