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

Carmen Kempka; Ryo Kikuchi; Koutarou Suzuki

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 circuits lower bound on linear garbling schemes semi-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}
}