CryptoDB
Efficient Arithmetic in Garbled Circuits
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2024 |
| Abstract: | 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 $\Z_m$ for any $m \geq 2$. Let $\ell = \lceil \log_2 m \rceil$ be the bit length of $\Z_m$ values. We garble arithmetic circuits over $\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. |
BibTeX
@inproceedings{eurocrypt-2024-33902,
title={Efficient Arithmetic in Garbled Circuits},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-58740-5_1},
author={David Heath},
year=2024
}