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 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 $$. Addition gates are free. Each multiplication gate costs $$ communication. Each bit-decomposition costs $$. $$ The second scheme targets mixed circuit modulo some $$. Each addition gate and multiplication gate costs $$. Every bit-decomposition costs $$. 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 $$, where addition gates are free, and each multiplication or bit-decomposition gate costs $$ communication. We improve on the recent work of Ball, Li, Lin, and Liu [Eurocrypt'23] which also relies on the DCR assumption.