Paper 2017/072
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in ASIACRYPT 2016
- Keywords
- garbled circuitslower bound on linear garbling schemessemi-private function evaluation
- Contact author(s)
- 9h358j30qe @ gmail com
- History
- 2017-02-03: received
- Short URL
- https://ia.cr/2017/072
- License
-
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},
url = {https://eprint.iacr.org/2017/072}
}
