U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

This is an archive
(replace .gov by .rip)
Presentation

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

November 5, 2020

Presenters

Xiao Wang - Northwestern University

Description

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. https://csrc.nist.rip/events/2020/mpts2020Joint work with Chun Guo and Jonathan Katz and Chenkai Weng and Yu Yu.

Event Details

Location

    
                            

Related Topics

Security and Privacy: cryptography

Created May 04, 2021, Updated June 07, 2021