International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations

Authors:
Hanjun Li , University of Washington
Tianren Liu , Peking University
Download:
DOI: 10.1007/978-3-031-58751-1_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
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 bit-decomposition 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: - 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 bit-decomposition costs $O(\lambda \cdot b^{2} / \log{b})$. - 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 bit-decomposition 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 bit-decomposition gate costs $O(\lambda_{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.
BibTeX
@inproceedings{eurocrypt-2024-33914,
  title={How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58751-1_12},
  author={Hanjun Li and Tianren Liu},
  year=2024
}