research-article

One Hot Garbling

Authors:

Vladimir KolesnikovAuthors Info & Claims

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Pages 574 - 593

https://doi.org/10.1145/3460120.3484764

Published: 13 November 2021 Publication History

Abstract

Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label. Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation and feed the resulting cleartext value back into the MPC. Such techniques are not known to work for GC. We show that it is, in fact, possible to improve GC efficiency, while keeping its round complexity, by exposing masked private values to the evaluator. %without introducing rounds of communication. Our improvements use garbled one-hot encodings of values. By using this encoding we improve a number of interesting functions, e.g., matrix multiplication, integer multiplication, field element multiplication, field inverses and AES S-Boxes, integer exponents, and more. We systematize our approach by providing a framework for designing such GC modules. Our constructions are concretely efficient. E.g., we improve binary matrix multiplication inside GC by more than 6x in terms of communication and by more than 4x in terms of WAN wall-clock time. Our improvement circumvents an important GC lower bound and may open GC to further improvement.

Supplementary Material

MP4 File (CCS21-fp235.mp4)

One hot garbling is an improvement to the classic Garbled Circuit Technique. In particular, one hot garbling constructs new and efficient Garbled Circuit gates. These new gates reduce the communication consumption of Garbled Circuits for many interesting functions.

Download
132.15 MB

References

[1]

David Archer, Victor Arribas Abril, Steve Lu, Pieter Maene, Nele Mertens, Danilo Sijacic, and Nigel Smart. 'bristol fashion' mpc circuits. https://homes.esat.kuleuven.be/ nsmart/MPC.

[2]

Benny Applebaum, Ivan Damgr ard, Yuval Ishai, Michael Nielsen, and Lior Zichron. Secure arithmetic computation with constant computational overhead. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 223--254. Springer, Heidelberg, August 2017.

[3]

Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 489--518. Springer, Heidelberg, August 2019.

[4]

Joan Boyar, Morris Dworkin, Rene Peralta, Meltem Turan, Cagdas Calik, and Luis Brandao. Circuit Minimization Work. http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html, 2020.

[5]

Elette Boyle, Shafi Goldwasser, and Ioana Ivan. Functional signatures and pseudorandom functions. In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 501--519. Springer, Heidelberg, March 2014.

[6]

Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. Efficient garbling from a fixed-key blockcipher. In 2013 IEEE Symposium on Security and Privacy, pages 478--492. IEEE Computer Society Press, May 2013.

Digital Library

[7]

Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, ACM CCS 2012, pages 784--796. ACM Press, October 2012.

[8]

Judit Bar-Ilan and Donald Beaver. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Piotr Rudnicki, editor, 8th ACM PODC, pages 201--209. ACM, August 1989.

[9]

Joan Boyar, Philip Matthews, and René Peralta. Logic minimization techniques with applications to cryptology. Journal of Cryptology, 26(2):280--312, April 2013.

Digital Library

[10]

Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In 22nd ACM STOC, pages 503--513. ACM Press, May 1990.

[11]

Marshall Ball, Tal Malkin, and Mike Rosulek. Garbling gadgets for Boolean and arithmetic circuits. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 565--577. ACM Press, October 2016.

[12]

Joan Boyar and René Peralta. A new combinational logic minimization technique with applications to cryptology. Experimental Algorithms Lecture Notes in Computer Science, page 178--189, 2010.

[13]

Dan Boneh and Brent Waters. Constrained pseudorandom functions and their applications. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 280--300. Springer, Heidelberg, December 2013.

[14]

Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, and Hong-Sheng Zhou. On the security of the “free-XOR” technique. In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 39--53. Springer, Heidelberg, March 2012.

[15]

Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables. In NDSS 2017. The Internet Society, February / March 2017.

[16]

Ivan Damgr ard, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. The TinyTable protocol for 2-party secure computation, or: Gate-scrambling revisited. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 167--187. Springer, Heidelberg, August 2017.

[17]

Jack Doerner and abhi shelat. Scaling ORAM for secure computation. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 523--535. ACM Press, October / November 2017.

Digital Library

[18]

Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions (extended abstract). In 25th FOCS, pages 464--479. IEEE Computer Society Press, October 1984.

[19]

Jorge Guajardo, Sandeep S. Kumar, Christof Paar, and Jan Pelzl. Efficient software-implementation of finite fields with applications to cryptography. In Acta Applicandae Mathematica, 2006.

[20]

Chun Guo, Jonathan Katz, Xiao Wang, and Yu Yu. Efficient and secure multiparty computation from fixed-key block ciphers. In 2020 IEEE Symposium on Security and Privacy, pages 825--841. IEEE Computer Society Press, May 2020.

[21]

Adam Groce, Alex Ledger, Alex J. Malozemoff, and Arkady Yerukhimovich. CompGC: Efficient offline/online semi-honest two-party computation. Cryptology ePrint Archive, Report 2016/458, 2016. https://eprint.iacr.org/2016/458.

[22]

Shay Gueron, Yehuda Lindell, Ariel Nof, and Benny Pinkas. Fast garbling of circuits under standard assumptions. Journal of Cryptology, 31(3):798--844, July 2018.

Digital Library

[23]

David Heath and Vladimir Kolesnikov. Stacked garbling - garbled circuit proportional to longest execution path. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 763--792. Springer, Heidelberg, August 2020.

[24]

David Heath and Vladimir Kolesnikov. Stacked garbling for disjunctive zero-knowledge proofs. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 569--598. Springer, Heidelberg, May 2020.

[25]

David Heath and Vladimir Kolesnikov. Logstack: Stacked garbling with o(b log b) computation. Cryptology ePrint Archive, Report 2021/531, 2021. https://eprint.iacr.org/2015/751.pdf.

[26]

David Heath, Vladimir Kolesnikov, and Stanislav Peceny. MOTIF: (almost) free branching in GMW - via vector-scalar multiplication. In ASIACRYPT 2020, Part III, LNCS, pages 3--30. Springer, Heidelberg, December 2020.

Digital Library

[27]

Wilko Henecka, Stefan Kögl, Ahmad-Reza Sadeghi, Thomas Schneider, and Immo Wehrenberg. TASTY: tool for automating secure two-party computations. In Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov, editors, ACM CCS 2010, pages 451--462. ACM Press, October 2010.

[28]

Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. On the power of correlated randomness in secure computation. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 600--620. Springer, Heidelberg, March 2013.

[29]

Marek Jawurek, Florian Kerschbaum, and Claudio Orlandi. Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 955--966. ACM Press, November 2013.

[30]

Matthew Kelly, Alan Kaminsky, Michael Kurdziel, Marcin, and Stanis?aw Radziszowski. Customizable sponge-based authenticated encryption using 16-bit s-boxes. In MILCOM 2015 - 2015 IEEE Military Communications Conference, pages 43--48, 2015.

Digital Library

[31]

W. Sean Kennedy, Vladimir Kolesnikov, and Gordon T. Wilfong. Overlaying conditional circuit clauses for secure computation. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 499--528. Springer, Heidelberg, December 2017.

[32]

Vladimir Kolesnikov, Payman Mohassel, and Mike Rosulek. FleXOR: Flexible garbling for XOR gates that beats free-XOR. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS, pages 440--457. Springer, Heidelberg, August 2014.

[33]

Vladimir Kolesnikov, Jesper Buus Nielsen, Mike Rosulek, Ni Trieu, and Roberto Trifiletti. DUPLO: Unifying cut-and-choose for garbled circuits. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 3--20. ACM Press, October / November 2017.

[34]

Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias. Delegatable pseudorandom functions and applications. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 669--684. ACM Press, November 2013.

[35]

Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP 2008, Part II, volume 5126 of LNCS, pages 486--498. Springer, Heidelberg, July 2008.

[36]

Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In Proceedings of the 1st ACM conference on Electronic commerce, pages 129--139. ACM, 1999.

Digital Library

[37]

Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure two-party computation is practical. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 250--267. Springer, Heidelberg, December 2009.

[38]

Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2. 0: Improved mixed-protocol secure two-party computation. Cryptology ePrint Archive, Report 2020/1225, 2020. https://eprint.iacr.org/2020/1225.

[39]

Mike Rosulek and Lawrence Roy. Three halves make a whole? Beating the half-gates lower bound for garbled circuits. LNCS, pages 94--124. Springer, Heidelberg, 2021.

[40]

M. Sadegh Riazi, Christian Weinert, Oleksandr Tkachenko, Ebrahim M. Songhori, Thomas Schneider, and Farinaz Koushanfar. Chameleon: A hybrid secure computation framework for machine learning applications. In Jong Kim, Gail-Joon Ahn, Seungjoo Kim, Yongdae Kim, Javier López, and Taesoo Kim, editors, ASIACCS 18, pages 707--721. ACM Press, April 2018.

[41]

Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, and Mariana Raykova. Distributed vector-OLE: Improved constructions and implementation. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, ACM CCS 2019, pages 1055--1072. ACM Press, November 2019.

[42]

Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit, 2016.

[43]

Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: Fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits. In IEEE Symposium on Security and Privacy, 2021.

[44]

Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. Ferret: Fast extension for correlated OT with small communication. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 20, pages 1607--1626. ACM Press, November 2020.

Digital Library

[45]

Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole - reducing data transfer in garbled circuits using half gates. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 220--250. Springer, Heidelberg, April 2015.

Cited By

Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402145
Gong BLau WAu MYang RXue HLi L(2024)Efficient Zero-Knowledge Arguments For Paillier Cryptosystem2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00093(1813-1831)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00093
Heath DKolesnikov VNg L(2024)Garbled Circuit Lookup Tables with Logarithmic Number of CiphertextsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_7(185-215)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_7
Show More Cited By

Index Terms

One Hot Garbling
1. Security and privacy
  1. Cryptography
2. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic protocols

Recommendations

Efficient Constant-Round Multi-party Computation Combining BMR and SPDZ

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of malicious adversaries. This is especially the case in the two-party setting, where constant-round protocols ...
Optimizing Semi-Honest Secure Multiparty Computation for the Internet
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

In the setting of secure multiparty computation, a set of parties with private inputs wish to compute some function of their inputs without revealing anything but their output. Over the last decade, the efficiency of secure two-party computation has ...
Fast Garbling of Circuits Under Standard Assumptions
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

November 2021

3558 pages

ISBN:9781450384544

DOI:10.1145/3460120

General Chairs:
Yongdae Kim
KAIST, Republic of Korea
,
Jong Kim
POSTECH, Republic of Korea
,
Program Chairs:
Giovanni Vigna
University of California, Santa Barbara / VMware, USA
,
Elaine Shi
Carnegie Mellon University, USA

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 the author(s) 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

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

CCS '21

Sponsor:

SIGSAC

CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security

November 15 - 19, 2021

Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
874
Total Downloads

Downloads (Last 12 months)179
Downloads (Last 6 weeks)4

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pohle EAbidin APreneel B(2024)Fast Evaluation of S-Boxes With Garbled CircuitsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.340214519(5530-5544)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3402145
Gong BLau WAu MYang RXue HLi L(2024)Efficient Zero-Knowledge Arguments For Paillier Cryptosystem2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00093(1813-1831)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00093
Heath DKolesnikov VNg L(2024)Garbled Circuit Lookup Tables with Logarithmic Number of CiphertextsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_7(185-215)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58740-5_7
Baressi Šegota SLorencin IKovač ZCar Z(2023)On Approximating the pIC50 Value of COVID-19 Medicines In Silico with Artificial Neural NetworksBiomedicines10.3390/biomedicines1102028411:2(284)Online publication date: 19-Jan-2023
https://doi.org/10.3390/biomedicines11020284
Balla SKoushanfar FMeng WJensen CCremers CKirda E(2023)HELiKs: HE Linear Algebra Kernels for Secure InferenceProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623136(2306-2320)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623136
Yang YPeceny SHeath DKolesnikov VMeng WJensen CCremers CKirda E(2023)Towards Generic MPC Compilers via Variable Instruction Set Architectures (VISAs)Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616664(2516-2530)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616664
Ng LChow S(2023)SoK: Cryptographic Neural-Network Computation2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179483(497-514)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179483
Guo XYang KWang XZhang WXie XZhang JLiu Z(2023)Half-Tree: Halving the Cost of Tree Expansion in COT and DPFAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30545-0_12(330-362)Online publication date: 23-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30545-0_12
Boyle ECouteau GGilboa NIshai YKohl LResch NScholl P(2022)Correlated Pseudorandomness from Expand-Accumulate CodesAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15979-4_21(603-633)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15979-4_21

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents