Welcome to the resource topic for 2017/072
Title:
How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes
Authors: Carmen Kempka, Ryo Kikuchi, 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.
ePrint: https://eprint.iacr.org/2017/072
Talk: https://www.youtube.com/watch?v=7V0e-IoMO_c
Slides: https://iacr.org/cryptodb/archive/2016/ASIACRYPT/presentation/27908.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .