Paper 2024/139

Efficient Arithmetic in Garbled Circuits

David Heath, University of Illinois Urbana-Champaign
Abstract

Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from heavy assumptions, such as LWE. We construct arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let λ denote a computational security parameter, and consider the integers Zm for any m2. Let =log2m be the bit length of Zm values. We garble arithmetic circuits over Zm where the garbling of each gate has size bits. Constrast this with Boolean-circuit-based arithmetic, requiring bits via the schoolbook multiplication algorithm, or bits via Karatsuba's algorithm. Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
Keywords
Secure Multiparty ComputationGarbled CircuitsArithmetic Circuits
Contact author(s)
daheath @ illinois edu
History
2024-02-02: approved
2024-01-31: received
See all versions
Short URL
https://ia.cr/2024/139
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/139,
      author = {David Heath},
      title = {Efficient Arithmetic in Garbled Circuits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/139},
      year = {2024},
      url = {https://eprint.iacr.org/2024/139}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.