Paper 2017/072

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

Carmen Kempka, Ryo Kikuchi, and Koutarou Suzuki


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.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2016
garbled circuitslower bound on linear garbling schemessemi-private function evaluation
Contact author(s)
9h358j30qe @ gmail com
2017-02-03: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.