Paper 2019/1168

Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)

Chun Guo, Jonathan Katz, Xiao Wang, Chenkai Weng, and Yu Yu

Abstract

We study the concrete security of high-performance implementations of half-gates garbling, which all rely on (hardware-accelerated)~AES. We find that current instantiations using $k$-bit wire labels can be completely broken---in the sense that the circuit evaluator learns all the inputs of the circuit garbler---in time $O(2^k/C)$, where $C$ is the total number of (non-free) gates that are garbled, possibly across multiple independent executions. The attack can be applied to existing circuit-garbling libraries using $k=80$ when $C \approx 10^9$, and would require 267 machine-months and cost about USD 3500 to implement on the Google Cloud Platform. Since the attack can be entirely parallelized, the attack could be carried out in about a month using $\approx 250$ machines. With this as our motivation, we seek a way to instantiate the hash function in the half-gates scheme so as to achieve better concrete security. We present a construction based on AES that achieves optimal security in the single-instance setting (when only a single circuit is garbled). We also show how to modify the half-gates scheme so that its concrete security does not degrade in the multi-instance setting. Our modified scheme is as efficient as prior work in networks with up to 2 Gbps bandwidth.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
garbled circuitideal cipher modelconcrete security
Contact author(s)
wangxiao @ cs northwestern edu
History
2019-10-08: received
Short URL
https://ia.cr/2019/1168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1168,
      author = {Chun Guo and Jonathan Katz and Xiao Wang and Chenkai Weng and Yu Yu},
      title = {Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1168},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1168}},
      url = {https://eprint.iacr.org/2019/1168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.