Paper 2025/207
Efficient Mixed Garbling from Homomorphic Secret Sharing and GGM-Tree
Abstract
We present new techniques for garbling mixed arithmetic and boolean circuits, utilizing the homomorphic secret sharing scheme introduced by Roy \& Singh (Crypto 2021), along with the half-tree protocol developed by Guo et al (Eurocrypt 2023). Compared to some two-party interactive protocols, our mixed garbling only requires several times $(<10)$ more communication cost. We construct the bit decomposition/composition gadgets with communication cost $O((\lambda+\lambda_{\text{DCR}}/k)b)$ for integers in the range $(-2^{b-1}, 2^{b-1})$, requiring $O(2^k)$ computations for the GGM-tree. Our approach is compatible with constant-rate multiplication protocols, and the cost decreases as $k$ increases. Even for a small $k=8$, the concrete efficiency ranges from $6\lambda b$ ($b \geq 1000$ bits) to $9\lambda b$ ($b \sim 100$ bits) per decomposition/composition. In addition, we develop the efficient gadgets for mod $q$ and unsigned truncation based on bit decomposition and composition. We construct efficient arithmetic gadgets over various domains. For bound integers, we improve the multiplication rate in the work of Meyer et al. (TCC 2024) from $\textstyle\frac{\zeta-2}{\zeta+1}$ to $\frac{\zeta-2}{\zeta}$. We propose new garbling schemes over other domains through bounded integers with our modular and truncation gadgets, which is more efficient than previous constructions. For $\mathbb{Z}_{2^b}$, additions and multiplication can be garbled with a communication cost comparable to our bit decomposition. For general finite field $\mathbb{F}_{p^n}$, particularly for large values of $p$ and $n$, we garble the addition and multiplication at the cost of $O((\lambda+\lambda_{\text{DCR}}/k)b)$, where $b = n\lceil \log p \rceil$. For applications to real numbers, we introduce an ``error-based'' truncation that makes the cost of multiplication dependent solely on the desired precision.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2025
- Keywords
- Garbled circuitMixed circuitsSecure computation
- Contact author(s)
-
guojian @ ntu edu sg
wenjie006 @ e ntu edu sg - History
- 2025-02-12: approved
- 2025-02-11: received
- See all versions
- Short URL
- https://ia.cr/2025/207
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/207, author = {Jian Guo and Wenjie Nan}, title = {Efficient Mixed Garbling from Homomorphic Secret Sharing and {GGM}-Tree}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/207}, year = {2025}, url = {https://eprint.iacr.org/2025/207} }