Paper 2017/072 Original: eprint.iacr.org/2017/072 ↗
How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes
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
- Preprint.
- History
- 2017-02-03: last updated
- 2017-02-03: published
- Short URL
- https://ia.cr/2017/072
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}