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

Chun Guo; Jonathan Katz; Xiao Wang; Chenkai Weng; Yu Yu

doi:10.1007/978-3-030-56880-1_28

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

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 ≈ 10⁹, 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 language	English (US)
Title of host publication	Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings
Editors	Daniele Micciancio, Thomas Ristenpart
Publisher	Springer
Pages	793-822
Number of pages	30
ISBN (Print)	9783030568795
DOIs	https://doi.org/10.1007/978-3-030-56880-1_28
State	Published - 2020
Event	40th Annual International Cryptology Conference, CRYPTO 2020 - Santa Barbara, United States Duration: Aug 17 2020 → Aug 21 2020

Publication series

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

Conference

Conference	40th Annual International Cryptology Conference, CRYPTO 2020
Country/Territory	United States
City	Santa Barbara
Period	8/17/20 → 8/21/20

Funding

Acknowledgments. The authors thank Mike Rosulek for his helpful feedback on the paper. Work of Chun Guo was supported by the Program of Qilu Young Scholars (Grant No. 61580089963177) of Shandong University, the National Natural Science Foundation of China (Grant No. 61602276), and the Shandong Nature Science Foundation of China (Grant No. ZR2016FM22). Work of Jonathan Katz was supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via 2019-1902070008. The views and conclusions herein are those of the authors and should not be interpreted as necessarily representing the official policies, expressed or implied, of ODNI, IARPA, or the U.S. Government. Work of Yu Yu was supported by the National Natural Science Foundation of China (Grant Nos. 61872236 and 61971192) and the National Cryptography Development Fund (Grant No. MMJJ20170209) and the National Key Research and Development Program of China (Grant No. 2018YFA0704701). Xiao Wang and Yu Yu also thank PlatON for their generous support.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-56880-1_28

Cite this

Guo, C., Katz, J., Wang, X., Weng, C., & Yu, Y. (2020). Better concrete security for half-gates garbling (in the multi-instance setting). In D. Micciancio, & T. Ristenpart (Eds.), Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings (pp. 793-822). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12171 LNCS). Springer. https://doi.org/10.1007/978-3-030-56880-1_28

Guo, Chun ; Katz, Jonathan ; Wang, Xiao et al. / Better concrete security for half-gates garbling (in the multi-instance setting). Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. editor / Daniele Micciancio ; Thomas Ristenpart. Springer, 2020. pp. 793-822 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{82c7b35de0ea4cdea02a7b638e978fa0,

title = "Better concrete security for half-gates garbling (in the multi-instance setting)",

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.",

author = "Chun Guo and Jonathan Katz and Xiao Wang and Chenkai Weng and Yu Yu",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020.; 40th Annual International Cryptology Conference, CRYPTO 2020 ; Conference date: 17-08-2020 Through 21-08-2020",

year = "2020",

doi = "10.1007/978-3-030-56880-1_28",

language = "English (US)",

isbn = "9783030568795",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "793--822",

editor = "Daniele Micciancio and Thomas Ristenpart",

booktitle = "Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings",

}

Guo, C, Katz, J, Wang, X, Weng, C & Yu, Y 2020, Better concrete security for half-gates garbling (in the multi-instance setting). in D Micciancio & T Ristenpart (eds), Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12171 LNCS, Springer, pp. 793-822, 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, United States, 8/17/20. https://doi.org/10.1007/978-3-030-56880-1_28

Better concrete security for half-gates garbling (in the multi-instance setting). / Guo, Chun; Katz, Jonathan; Wang, Xiao et al.
Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. ed. / Daniele Micciancio; Thomas Ristenpart. Springer, 2020. p. 793-822 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12171 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Guo, Chun

AU - Katz, Jonathan

AU - Wang, Xiao

AU - Weng, Chenkai

AU - Yu, Yu

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85089717063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85089717063&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-56880-1_28

DO - 10.1007/978-3-030-56880-1_28

M3 - Conference contribution

AN - SCOPUS:85089717063

SN - 9783030568795

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 793

EP - 822

BT - Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings

A2 - Micciancio, Daniele

A2 - Ristenpart, Thomas

PB - Springer

T2 - 40th Annual International Cryptology Conference, CRYPTO 2020

Y2 - 17 August 2020 through 21 August 2020

ER -

Guo C, Katz J, Wang X, Weng C, Yu Y. Better concrete security for half-gates garbling (in the multi-instance setting). In Micciancio D, Ristenpart T, editors, Advances in Cryptology - CRYPTO 2020 - 40th Annual International Cryptology Conference, CRYPTO 2020, Proceedings. Springer. 2020. p. 793-822. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-56880-1_28

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

Abstract

Publication series

Conference

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this