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

Carmen Kempka, 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.

Available format(s)
Category
Foundations
Publication info
Keywords
garbled circuitslower bound on linear garbling schemessemi-private function evaluation
Contact author(s)
9h358j30qe @ gmail com
History
Short URL
https://ia.cr/2017/072

CC BY

BibTeX

@misc{cryptoeprint:2017/072,
author = {Carmen Kempka and Ryo Kikuchi and Koutarou Suzuki},
title = {How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes},
howpublished = {Cryptology ePrint Archive, Paper 2017/072},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/072}},
url = {https://eprint.iacr.org/2017/072}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.