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
Date: received 31 Jan 2017
Contact author: 9h358j30qe at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20170203:185742 (All versions of this report)
Short URL: ia.cr/2017/072
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]