Hash-Enabled Garbling and the Insecurity of Free-Hashing Garbled Circuits
Authors: 
Ruiyu Zhu, Yan HuangAuthors Info & Claims
Pages 488 - 500
Abstract
Hashing garbled circuits is an important, albeit expensive, bandwidth- saving technique that can be an order-of-magnitude slower than generating garbled circuits. In a recent work, Fan et al. (EURO- CRYPT, 2017) proposed a method to produce GC-hashes with- out any calls to expensive collision-resistant hash functions. They showed experimentally that the overhead of hashing GCs can be eliminated almost entirely.
In this paper, we identify several security flaws in their approach. (1) We show some fundamental weakness in the notion of hash-security, which makes it impossible to support any existing malicious GC-hash-based cut-and-choose protocols. (2) Although the concept of hash-security could be useful in certain scenarios, we show (with concrete attacks) that the Free-Hash construction given in their paper is not really hash-secure.
As a positive result of this work, we propose and formalize the concept of hash-enabled garbling and show how an actively-secure 2PC protocol can be constructed with black-box use of any hash- enabled garbling scheme. This is the first time when the use of GC-hashes in any cut-and-choose protocols is formally examined and rigorously proved secure. Our protocol allows to leverage GC- hashes to save bandwidth while minimizing the cut-and-choose duplication factor, i.e., using s (instead of 3s) copies of GCs to achieve 2-s statistical security.
References
[1]
Arash Afshar, Payman Mohassel, Benny Pinkas, and Ben Riva. 2014. Non-interactive secure computation based on cut-and-choose. In EUROCRYPT.
[2]
Yonatan Aumann and Yehuda Lindell. 2007. Security against covert adversaries: efficient protocols for realistic adversaries. In TCC.
[3]
Donald Beaver, Silvio Micali, and Phillip Rogaway. 1990. The round complexity of secure protocols. In STOC.
[4]
Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. 2013. Efficient garbling from a fixed-key blockcipher. In IEEE S&P.
[5]
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. 2012. Foundations of garbled circuits. In ACM CCS.
[6]
Lu'is Brand ao. 2013. Secure two-party computation with reusable bit-commitments via cut-and-choose with forge-and-lose technique. In ASIACRYPT.
[7]
Jan Camenisch and Anna Lysyanskaya. 2001. An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT.
[8]
Melissa Chase, Chaya Ganesh, and Payman Mohassel. 2016. Efficient zero-knowledge proof of algebraic and non-algebraic statements with applications to privacy preserving credentials. In CRYPTO.
[9]
Xiong Fan, Chaya Ganesh, and Vladimir Kolesnikov. 2017. Hashing Garbled Circuits for Free. In EUROCRYPT.
[10]
Tore Frederiksen, Thomas Jakobsen, Jesper Nielsen, Peter Nordholt, and Claudio Orlandi. 2013. Minilego: Efficient secure two-party computation from general assumptions. In EUROCRYPT.
[11]
Tore Kasper Frederiksen, Jesper Nielsen, and Claudio Orlandi. 2015. Privacy-free garbled circuits with applications to efficient zero-knowledge. In EUROCRYPT.
[12]
Vipul Goyal, Payman Mohassel, and Adam Smith. 2008. Efficient two party and multi party computation against covert adversaries. In EUROCRYPT.
[13]
Shay Gueron, Yehuda Lindell, Ariel Nof, and Benny Pinkas. 2015. Fast garbling of circuits under standard assumptions. In ACM CCS.
[14]
Chun Guo, Jonathan Katz, Xiao Wang, and Yu Yu. 2019. Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers. In IEEE S&P.
[15]
Cheng Hong, Jonathan Katz, Vladimir Kolesnikov, Wen-jie Lu, and Xiao Wang. 2019. Covert security with public verifiability: faster, leaner, and simpler. In EUROCRYPT.
[16]
Yan Huang, David Evans, Jonathan Katz, and Lior Malka. 2011. Faster secure two-party computation using garbled circuits. In USENIX Security.
[17]
Yan Huang, Jonathan Katz, and David Evans. 2013. Efficient secure two-party computation using symmetric cut-and-choose. In CRYPTO.
[18]
Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2015. Actively secure OT extension with optimal overhead. In CRYPTO.
[19]
Vladimir Kolesnikov, Hugo Krawczyk, Yehuda Lindell, Alex Malozemoff, and Tal Rabin. 2016. Attribute-based key exchange with general policies. In ACM CCS.
[20]
Vladimir Kolesnikov and Alex J Malozemoff. 2015. Public verifiability in the covert model (almost) for free. In ASIACRYPT.
[21]
Vladimir Kolesnikov, Payman Mohassel, and Mike Rosulek. 2014. FleXOR: Flexible garbling for XOR gates that beats free-XOR. In CRYPTO.
[22]
Vladimir Kolesnikov, Jesper Nielsen, Mike Rosulek, Ni Trieu, and Roberto Trifiletti. 2017. DUPLO: unifying cut-and-choose for garbled circuits. In ACM CCS.
[23]
Vladimir Kolesnikov and Thomas Schneider. 2008. Improved garbled circuit: Free XOR gates and applications. In ICALP.
[24]
Benjamin Kreuter, Abhi Shelat, and Chih-Hao Shen. 2012. Billion-Gate Secure Computation with Malicious Adversaries. In USENIX Security.
[25]
Yehuda Lindell. 2016. Fast cut-and-choose-based protocols for malicious and covert adversaries. Journal of Cryptology (2016).
[26]
Yehuda Lindell and Benny Pinkas. 2007. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In EUROCRYPT.
[27]
Yehuda Lindell and Benny Pinkas. 2011. Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer. In TCC.
[28]
Yehuda Lindell and Benny Pinkas. 2012. Secure two-party computation via cut-and-choose oblivious transfer. Journal of Cryptology (2012).
[29]
Yehuda Lindell and Ben Riva. 2014. Cut-and-choose Yao-based secure computation in the online/offline and batch settings. In CRYPTO.
[30]
Yehuda Lindell and Ben Riva. 2015. Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In ACM CCS.
[31]
Dahlia Malkhi, Noam Nisan, Benny Pinkas, Yaron Sella, et al. 2004. Fairplay-Secure Two-Party Computation System. In USENIX Security.
[32]
Payman Mohassel and Ben Riva. 2013. Garbled circuits checking garbled circuits: More efficient and secure two-party computation. In CRYPTO.
[33]
Jesper Nielsen, Thomas Schneider, and Roberto Trifiletti. 2017. Constant Round Maliciously Secure 2PC with Function-independent Preprocessing using LEGO. In NDSS.
[34]
Benny Pinkas, Thomas Schneider, Nigel P Smart, and Stephen C Williams. 2009. Secure two-party computation is practical. In ASIACRYPT.
[35]
Peter Rindal and Mike Rosulek. 2016. Faster Malicious 2-Party Secure Computation with Online/Offline Dual Execution. In USENIX Security.
[36]
Chih-hao Shen and Abhi Shelat. 2011. Two-output secure computation with malicious adversaries. In EUROCRYPT.
[37]
Chih-hao Shen and Abhi Shelat. 2013. Fast two-party secure computation with minimal assumptions. In ACM CCS. ACM.
[38]
Xiao Wang, Alex J Malozemoff, and Jonathan Katz. 2017a. Faster secure two-party computation in the single-execution setting. In EUROCRYPT.
[39]
Xiao Wang, Samuel Ranellucci, and Jonathan Katz. 2017b. Authenticated garbling and efficient maliciously secure two-party computation. In ACM CCS.
[40]
Samee Zahur, Mike Rosulek, and David Evans. 2015. Two halves make a whole -- Reducing Data Transfer in Garbled Circuits Using Half Gates. In EUROCRYPT.
[41]
Ruiyu Zhu, Darion Cassel, Amr Sabry, and Yan Huang. 2018. NANOPI: Extreme-Scale Actively-Secure Multi-Party Computation. In ACM CCS.
[42]
Ruiyu Zhu and Yan Huang. 2017. JIMU: faster LEGO-based secure computation using additive homomorphic hashes. In ASIACRYPT.
[43]
Ruiyu Zhu, Yan Huang, and Darion Cassel. 2017. Pool: scalable on-demand secure computation service against malicious adversaries. In ACM CCS.
Index Terms
- Hash-Enabled Garbling and the Insecurity of Free-Hashing Garbled Circuits
Recommendations
Foundations of garbled circuits
CCS '12: Proceedings of the 2012 ACM conference on Computer and communications securityGarbled circuits, a classical idea rooted in the work of Yao, have long been understood as a cryptographic technique, not a cryptographic goal. Here we cull out a primitive corresponding to this technique. We call it a garbling scheme. We provide a ...
Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently
CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications securityZero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) ...
On Multiparty Garbling of Arithmetic Circuits
Advances in Cryptology – ASIACRYPT 2018AbstractWe initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2021
975 pages
ISBN:9781450382878
DOI:10.1145/3433210
- General Chairs:
- Jiannong Cao,
- Man Ho Au,
- Program Chairs:
- Zhiqiang Lin,
- Moti Yung
Copyright © 2021 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 June 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Alibaba Innovative Research
Conference
ASIA CCS '21
Sponsor:
ASIA CCS '21: ACM Asia Conference on Computer and Communications Security
June 7 - 11, 2021
Virtual Event, Hong Kong
Acceptance Rates
Overall Acceptance Rate 418 of 2,322 submissions, 18%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 118Total Downloads
- Downloads (Last 12 months)12
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in