Better concrete security for half-gates garbling (in the multi-instance setting)

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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(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 ≈ 109, and would require 267 machine-months and cost about $3500 to implement on the Google Cloud Platform. Since the attack can be fully parallelized, it 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings
EditorsDaniele Micciancio, Thomas Ristenpart
PublisherSpringer
Pages793-822
Number of pages30
ISBN (Print)9783030568795
DOIs
StatePublished - 2020
Event40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States
Duration: Aug 17 2020Aug 21 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12171 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference40th Annual International Cryptology Conference, CRYPTO 2020
CountryUnited States
CitySanta Barbara
Period8/17/208/21/20

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Better concrete security for half-gates garbling (in the multi-instance setting)'. Together they form a unique fingerprint.

Cite this