Paper 2025/207

Efficient Mixed Garbling from Homomorphic Secret Sharing and GGM-Tree

Jian Guo, Nanyang Technological University
Wenjie Nan, Nanyang Technological University
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 for integers in the range , requiring computations for the GGM-tree. Our approach is compatible with constant-rate multiplication protocols, and the cost decreases as increases. Even for a small , the concrete efficiency ranges from ( bits) to ( bits) per decomposition/composition. In addition, we develop the efficient gadgets for mod 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 to . 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 , additions and multiplication can be garbled with a communication cost comparable to our bit decomposition. For general finite field , particularly for large values of and , we garble the addition and multiplication at the cost of , where . 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.