## CryptoDB

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

Authors: Chun Guo , School of Cyber Science and Technology, Shandong University Jonathan Katz , George Mason University Xiao Wang , Northwestern University Chenkai Weng , Northwestern University Yu Yu , Shanghai Jiao Tong University DOI: http://dx.doi.org/10.1007/978-3-030-56880-1_28 (login may be required) Search ePrint Search Google Slides CRYPTO 2020 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(2k/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 ≈ $10^9$, and would require 267 machine-months and cost about \$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 ≈ 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.
##### BibTeX
@inproceedings{crypto-2020-30377,
title={Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)},
publisher={Springer-Verlag},
doi={http://dx.doi.org/10.1007/978-3-030-56880-1_28},
author={Chun Guo and Jonathan Katz and Xiao Wang and Chenkai Weng and Yu Yu},
year=2020
}