Paper 2024/369
Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts
Abstract
Garbled Circuit (GC) is a basic technique for practical secure computation. GC handles Boolean circuits; it consumes significant network bandwidth to transmit encoded gate truth tables, each of which scales with the computational security parameter $\kappa$. GC optimizations that reduce bandwidth consumption are valuable. It is natural to consider a generalization of Boolean two-input one-output gates (represented by $4$-row one-column lookup tables, LUTs) to arbitrary $N$-row $m$-column LUTs. Known techniques for this do not scale, with naive size-$O(Nm\kappa)$ garbled LUT being the most practical approach in many scenarios. Our novel garbling scheme -- logrow -- implements GC LUTs while sending only a logarithmic in $N$ number of ciphertexts! Specifically, let $n = \lceil \log_2 N \rceil$. We allow the GC parties to evaluate a LUT for $(n-1)\kappa + nm\kappa + Nm$ bits of communication. logrow is compatible with modern GC advances, e.g. half gates and free XOR. Our work improves state-of-the-art GC handling of several interesting applications, such as privacy-preserving machine learning, floating-point arithmetic, and DFA evaluation.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A minor revision of an IACR publication in EUROCRYPT 2024
- Keywords
- Multiparty ComputationGarbled CircuitsLookup Tables
- Contact author(s)
-
daheath @ illinois edu
kolesnikov @ gatech edu
kng68 @ gatech edu - History
- 2024-03-01: approved
- 2024-02-28: received
- See all versions
- Short URL
- https://ia.cr/2024/369
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/369, author = {David Heath and Vladimir Kolesnikov and Lucien K. L. Ng}, title = {Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/369}, year = {2024}, url = {https://eprint.iacr.org/2024/369} }