Paper 2023/1584
How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations
Abstract
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 bitdecomposition 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: $\bullet$ 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 bitdecomposition costs $O(\lambda \cdot b^{2} / \log{b})$. $\bullet$ 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 bitdecomposition 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 bitdecomposition gate costs $O(\lambda_{\text{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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 garbled circuitssecure computationarithmetic circuitsmixed circuits
 Contact author(s)

hanjul @ cs washington edu
trl @ pku edu cn  History
 20231013: approved
 20231013: received
 See all versions
 Short URL
 https://ia.cr/2023/1584
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1584, author = {Hanjun Li and Tianren Liu}, title = {How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations}, howpublished = {Cryptology ePrint Archive, Paper 2023/1584}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1584}}, url = {https://eprint.iacr.org/2023/1584} }