Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


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

November 5, 2020


Xiao Wang - Northwestern University


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 gates, possibly across multiple independent executions. The attack can be applied to existing circuit-garbling libraries using k = 80 and would require 267 machine-months and cost about USD 3500. With this as our motivation, we seek a way to instantiate the hash function in the half-gates scheme 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.

Presented at

NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2020. work with Chun Guo and Jonathan Katz and Chenkai Weng and Yu Yu.

Event Details



Related Topics

Security and Privacy: cryptography

Created May 04, 2021, Updated June 07, 2021