Welcome to the resource topic for 2024/369
Title:
Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts
Authors: David Heath, Vladimir Kolesnikov, Lucien K. L. Ng
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.
ePrint: https://eprint.iacr.org/2024/369
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .