Paper 2023/1584

How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations

Hanjun Li, University of Washington
Tianren Liu, Peking University

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: $\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 bit-decomposition 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 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_{\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.

Available format(s)
Publication info
garbled circuitssecure computationarithmetic circuitsmixed circuits
Contact author(s)
hanjul @ cs washington edu
trl @ pku edu cn
2023-10-13: approved
2023-10-13: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.