Paper 2024/369

Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts

David Heath, University of Illinois Urbana-Champaign
Vladimir Kolesnikov, Georgia Institute of Technology
Lucien K. L. Ng, Georgia Institute of Technology
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.