TY - GEN
T1 - Garbled Circuit Lookup Tables with Logarithmic Number of Ciphertexts
AU - Heath, David
AU - Kolesnikov, Vladimir
AU - Ng, Lucien K.L.
N1 - This research was developed with funding from a Visa research award, a Cisco research award, a USDA APHIS research award (under opportunity number USDA-APHIS-10025-VSSP0000-23-0003), and NSF awards CNS-2246353, CNS-2246354, and CCF-2217070.
PY - 2024
Y1 - 2024
N2 - 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 κ. 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κ) 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=⌈log2N⌉. We allow the GC parties to evaluate a LUT for (n-1)κ+nmκ+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.
AB - 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 κ. 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κ) 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=⌈log2N⌉. We allow the GC parties to evaluate a LUT for (n-1)κ+nmκ+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.
KW - Garbled Circuits
KW - Lookup Tables
KW - Multiparty Computation
UR - http://www.scopus.com/inward/record.url?scp=85193604663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85193604663&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-58740-5_7
DO - 10.1007/978-3-031-58740-5_7
M3 - Conference contribution
AN - SCOPUS:85193604663
SN - 9783031587399
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 215
BT - Advances in Cryptology – EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2024, Proceedings
A2 - Joye, Marc
A2 - Leander, Gregor
PB - Springer
T2 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2024
Y2 - 26 May 2024 through 30 May 2024
ER -