Welcome to the resource topic for 2019/1168
Title:
Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)
Authors: Chun Guo, Jonathan Katz, Xiao Wang, Chenkai Weng, 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.
ePrint: https://eprint.iacr.org/2019/1168
Talk: https://www.youtube.com/watch?v=MKGqA0K9d8M
Slides: https://iacr.org/submit/files/slides/2020/crypto/crypto2020/199/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .