Efficient Arithmetic in Garbled Circuits

Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE. We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let \(\lambda \) denote a security parameter, and consider the integers \(\mathbb {Z}_m\) for any \(m \ge 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. Contrast 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.