Welcome to the resource topic for 2024/139
Title:
Efficient Arithmetic in Garbled Circuits
Authors: David Heath
Abstract:Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from heavy assumptions, such as LWE.
We construct arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let \lambda denote a computational security parameter, and consider the integers \mathbb{Z}_m for any m \geq 2. Let \ell = \lceil \log_2 m \rceil be the bit length of \mathbb{Z}_m values. We garble arithmetic circuits over \mathbb{Z}_m where the garbling of each gate has size O(\ell \cdot \lambda) bits. Constrast this with Boolean-circuit-based arithmetic, requiring O(\ell^2\cdot \lambda) bits via the schoolbook multiplication algorithm, or O(\ell^{1.585}\cdot \lambda) bits via Karatsuba’s algorithm.
Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.
ePrint: https://eprint.iacr.org/2024/139
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 .