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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-662-53890-6_32 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
Garbled circuits,Lower bound on linear garbling schemes,Semi-private function evaluation | Journal | 2017 |
ISSN | Citations | PageRank |
0302-9743 | 4 | 0.39 |
References | Authors | |
23 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Carmen Kempka | 1 | 6 | 0.75 |
Ryo Kikuchi | 2 | 46 | 9.37 |
Koutarou Suzuki | 3 | 518 | 29.57 |