## Cryptology ePrint Archive: Report 2017/072

How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes

Carmen Kempka and Ryo Kikuchi and Koutarou Suzuki

Abstract: At EUROCRYPT 2015, Zahur et al.\ argued that all linear, and thus, efficient, garbling schemes need at least two $k$-bit elements to garble an AND gate with security parameter $k$. We show how to circumvent this lower bound, and propose an efficient garbling scheme which requires less than two $k$-bit elements per AND gate for most circuit layouts. Our construction slightly deviates from the linear garbling model, and constitutes no contradiction to any claims in the lower-bound proof. With our proof of concept construction, we hope to spur new ideas for more practical garbling schemes. Our construction can directly be applied to semi-private function evaluation by garbling XOR, XNOR, NAND, OR, NOR and AND gates in the same way, and keeping the evaluator oblivious of the gate function.

Category / Keywords: foundations / garbled circuits, lower bound on linear garbling schemes, semi-private function evaluation

Original Publication (in the same form): IACR-ASIACRYPT-2016