Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts

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 naïve size- \(O(Nm\kappa )\) garbled LUT being the most practical approach in many scenarios. Our novel garbling scheme – \(\textsf{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. \(\textsf{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.