Welcome to the resource topic for 2023/1584
Title:
How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations
Authors: Hanjun Li, Tianren Liu
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:
\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.
ePrint: https://eprint.iacr.org/2023/1584
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .