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:

[ Cryptology ePrint archive ]