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 $$-row one-column lookup tables, LUTs) to arbitrary $$-row $$-column LUTs. Known techniques for this do not scale, with naive size-$$ garbled LUT being the most practical approach in many scenarios. Our novel garbling scheme -- logrow -- implements GC LUTs while sending only a logarithmic in $$ number of ciphertexts! Specifically, let $$. We allow the GC parties to evaluate a LUT for $$ 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.