{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:32:32Z","timestamp":1780633952460,"version":"3.54.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T00:00:00Z","timestamp":1691020800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T00:00:00Z","timestamp":1691020800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005714","name":"Technische Universit\u00e4t Darmstadt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005714","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao\u00a0(FOCS\u201986) and generalized to the multi-party setting by Beaver, Micali and Rogaway\u00a0(STOC\u201990). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler\u00a0(USENIX\u00a0Security\u201904), several implementation frameworks decoupled the task of compiling the function to be evaluated into a Boolean circuit from the engine that securely evaluates that circuit, e.g., using a secure two-party computation protocol based on garbled circuits. In this paper, we show that this decoupling of circuit generation and evaluation allows a subtle attack on several prominent garbling schemes. It occurs when violating the implicit assumption on the circuit that gates have different input wires which is most often not explicitly specified in the respective papers. The affected garbling schemes use separate calls to a deterministic encryption function for the left and right input wire of a gate to derive pseudo-random encryption pads that are XORed together. When a circuit contains a gate where the left and right input wire are the same, these two per-wire encryption pads cancel out and we demonstrate that this can result in a complete break of privacy. We show how the vulnerable garbling schemes can be fixed easily.<\/jats:p>","DOI":"10.1007\/s00145-023-09472-4","type":"journal-article","created":{"date-parts":[[2023,8,3]],"date-time":"2023-08-03T16:01:42Z","timestamp":1691078502000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Breaking and Fixing Garbled Circuits When a Gate has Duplicate Input Wires"],"prefix":"10.1007","volume":"36","author":[{"given":"Raine","family":"Nieminen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,8,3]]},"reference":[{"key":"9472_CR1","doi-asserted-by":"crossref","unstructured":"J.B. Almeida, M.\u00a0Barbosa, G.\u00a0Barthe, F.\u00a0Dupressoir, B.\u00a0Gr\u00e9goire, V.\u00a0Laporte, V.\u00a0Pereira, A fast and verified software stack for secure function evaluation, in CCS (2017)","DOI":"10.1145\/3133956.3134017"},{"key":"9472_CR2","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver, S.\u00a0Micali, P.\u00a0Rogaway, The round complexity of secure protocols, in STOC (1990)","DOI":"10.1145\/100216.100287"},{"key":"9472_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, V.T. Hoang, S.\u00a0Keelveedhi, P.\u00a0Rogaway, Efficient garbling from a fixed-key blockcipher, in S &P (2013)","DOI":"10.1109\/SP.2013.39"},{"key":"9472_CR4","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, V.T. Hoang, P.\u00a0Rogaway, Foundations of garbled circuits, in CCS (2012). Full version: https:\/\/ia.cr\/2012\/265","DOI":"10.1145\/2382196.2382279"},{"key":"9472_CR5","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ben-David, N.\u00a0Nisan, B.\u00a0Pinkas, FairplayMP: A system for secure multi-party computation, in CCS (2008)","DOI":"10.1145\/1455770.1455804"},{"key":"9472_CR6","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ben-Efraim, Y.\u00a0Lindell, E.\u00a0Omri, Optimizing semi-honest secure multiparty computation for the Internet, in CCS (2016)","DOI":"10.1145\/2976749.2978347"},{"key":"9472_CR7","doi-asserted-by":"crossref","unstructured":"A.\u00a0Ben-Efraim, Y.\u00a0Lindell, E.\u00a0Omri, Efficient scalable constant-round MPC via garbled circuits, in ASIACRYPT (2017)","DOI":"10.1007\/978-3-319-70697-9_17"},{"key":"9472_CR8","doi-asserted-by":"crossref","unstructured":"N.\u00a0B\u00fcscher, D.\u00a0Demmler, S.\u00a0Katzenbeisser, D.\u00a0Kretzmer, T.\u00a0Schneider, HyCC: Compilation of hybrid protocols for practical secure computation, in CCS (2018)","DOI":"10.1145\/3243734.3243786"},{"key":"9472_CR9","doi-asserted-by":"crossref","unstructured":"S.G. Choi, J.\u00a0Katz, R.\u00a0Kumaresan, H.-S. Zhou, On the security of the \u201cFree-XOR\u201d technique, in TCC (2012)","DOI":"10.1007\/978-3-642-28914-9_3"},{"key":"9472_CR10","doi-asserted-by":"crossref","unstructured":"D.\u00a0Demmler, T.\u00a0Schneider, M.\u00a0Zohner, ABY\u2014A framework for efficient mixed-protocol secure two-party computation, in NDSS (2015)","DOI":"10.14722\/ndss.2015.23113"},{"key":"9472_CR11","doi-asserted-by":"crossref","unstructured":"M.\u00a0Franz, A.\u00a0Holzer, S.\u00a0Katzenbeisser, C.\u00a0Schallhart, H.\u00a0Veith, CBMC-GC: An ANSI C compiler for secure two-party computations, in Compiler Construction\u00a0(CC) (2014)","DOI":"10.1007\/978-3-642-54807-9_15"},{"key":"9472_CR12","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Micali, A.\u00a0Wigderson, How to play ANY mental game, in STOC (1987)","DOI":"10.1145\/28395.28420"},{"key":"9472_CR13","doi-asserted-by":"crossref","unstructured":"S.\u00a0Gueron, Y.\u00a0Lindell, A.\u00a0Nof, B.\u00a0Pinkas, Fast garbling of circuits under standard assumptions, in CCS (2015)","DOI":"10.1145\/2810103.2813619"},{"key":"9472_CR14","doi-asserted-by":"crossref","unstructured":"W.\u00a0Henecka, S.\u00a0K\u00f6gl, A.\u00a0Sadeghi, T.\u00a0Schneider, I.\u00a0Wehrenberg, TASTY: Tool for automating secure two-party computations, in CCS (2010)","DOI":"10.1145\/1866307.1866358"},{"key":"9472_CR15","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Huang, D.\u00a0Evans, J.\u00a0Katz, L.\u00a0Malka, Faster secure two-party computation using garbled circuits, in USENIX Security (2011)","DOI":"10.1007\/978-3-642-25560-1_2"},{"key":"9472_CR16","doi-asserted-by":"crossref","unstructured":"K.\u00a0J\u00e4rvinen, V.\u00a0Kolesnikov, A.\u00a0Sadeghi, T.\u00a0Schneider, Embedded SFE: Offloading server and network using hardware tokens, in FC (2010)","DOI":"10.1007\/978-3-642-14577-3_17"},{"key":"9472_CR17","unstructured":"M.\u00a0Kiraz, B.\u00a0Schoenmakers, A protocol issue for the malicious case of Yao\u2019s garbled circuit construction, in Information Theory in the Benelux\u00a0(SITB) (2006)"},{"key":"9472_CR18","unstructured":"V.\u00a0Kolesnikov, T.\u00a0Schneider, Improved garbled circuit: Free XOR gates and applications, in ICALP (2008)"},{"key":"9472_CR19","unstructured":"B.\u00a0Kreuter, A.\u00a0Shelat, B.\u00a0Mood, K.\u00a0Butler, PCF: A portable circuit format for scalable two-party secure computation, in USENIX Security (2013)"},{"key":"9472_CR20","unstructured":"B.\u00a0Kreuter, A.\u00a0Shelat, C.\u00a0Shen, Billion-gate secure computation with malicious adversaries, in USENIX Security (2012)"},{"key":"9472_CR21","doi-asserted-by":"crossref","unstructured":"I.\u00a0Levi, C.\u00a0Hazay, Garbled circuits from an SCA perspective: Free XOR can be quite expensive..., in CHES (2023)","DOI":"10.46586\/tches.v2023.i2.54-79"},{"key":"9472_CR22","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Lindell, B.\u00a0Pinkas, An efficient protocol for secure two-party computation in the presence of malicious adversaries, in EUROCRYPT (2007)","DOI":"10.1007\/978-3-540-72540-4_4"},{"key":"9472_CR23","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Lindell, B.\u00a0Pinkas, A proof of security of Yao\u2019s protocol for two-party computation. J.\u00a0Cryptol. (2009)","DOI":"10.1007\/s00145-008-9036-8"},{"key":"9472_CR24","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Lindell, B.\u00a0Pinkas, Secure two-party computation via cut-and-choose oblivious transfer. J.\u00a0Cryptol. (2012)","DOI":"10.1007\/978-3-642-19571-6_20"},{"key":"9472_CR25","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Lindell, B.\u00a0Pinkas, N.P. Smart, Implementing two-party computation efficiently with security against malicious adversaries, in SCN (2008)","DOI":"10.1007\/978-3-540-85855-3_2"},{"key":"9472_CR26","doi-asserted-by":"crossref","unstructured":"C.\u00a0Liu, X.S. Wang, K.\u00a0Nayak, Y.\u00a0Huang, E.\u00a0Shi, ObliVM: A programming framework for secure computation, in S &P (2015)","DOI":"10.1109\/SP.2015.29"},{"key":"9472_CR27","doi-asserted-by":"crossref","unstructured":"L.\u00a0Malka, VMCrypt: Modular software architecture for scalable secure computation, in CCS (2011)","DOI":"10.1145\/2046707.2046787"},{"key":"9472_CR28","unstructured":"D.\u00a0Malkhi, N.\u00a0Nisan, B.\u00a0Pinkas, Y.\u00a0Sella, Fairplay\u2014Secure two-party computation system, in USENIX Security (2004)"},{"key":"9472_CR29","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mood, D.\u00a0Gupta, H.\u00a0Carter, K.\u00a0Butler, P.\u00a0Traynor, Frigate: A validated, extensible, and efficient compiler and interpreter for secure computation, in EuroS &P (2016)","DOI":"10.1109\/EuroSP.2016.20"},{"key":"9472_CR30","doi-asserted-by":"crossref","unstructured":"B.\u00a0Mood, L.\u00a0Letaw, K.\u00a0Butler, Memory-efficient garbled circuit generation for mobile devices, in FC (2012)","DOI":"10.1007\/978-3-642-32946-3_19"},{"key":"9472_CR31","doi-asserted-by":"crossref","unstructured":"M.\u00a0Naor, B.\u00a0Pinkas, R.\u00a0Sumner, Privacy preserving auctions and mechanism design, in Electronic Commerce\u00a0(EC) (1999)","DOI":"10.1145\/336992.337028"},{"key":"9472_CR32","doi-asserted-by":"crossref","unstructured":"B.\u00a0Pinkas, Fair secure two-party computation, in EUROCRYPT (2003)","DOI":"10.1007\/3-540-39200-9_6"},{"key":"9472_CR33","doi-asserted-by":"crossref","unstructured":"B.\u00a0Pinkas, T.\u00a0Schneider, N.P. Smart, S.C. Williams, Secure two-party computation is practical, in ASIACRYPT (2009)","DOI":"10.1007\/978-3-642-10366-7_15"},{"key":"9472_CR34","doi-asserted-by":"crossref","unstructured":"A.\u00a0Rastogi, M.A. Hammer, M.\u00a0Hicks, Wysteria: A programming language for generic, mixed-mode multiparty computations, in S &P (2014)","DOI":"10.1109\/SP.2014.48"},{"key":"9472_CR35","doi-asserted-by":"crossref","unstructured":"A.\u00a0Rastogi, N.\u00a0Swamy, M.\u00a0Hicks, Wys*: A DSL for verified secure multi-party computations, in Principles of Security and Trust\u00a0(POST) (2019)","DOI":"10.1007\/978-3-030-17138-4_5"},{"key":"9472_CR36","doi-asserted-by":"crossref","unstructured":"M.\u00a0Rosulek, L.\u00a0Roy, Three halves make a whole? Beating the half\u2013gates lower bound for garbled circuits, in CRYPTO (2021)","DOI":"10.1007\/978-3-030-84242-0_5"},{"key":"9472_CR37","doi-asserted-by":"crossref","unstructured":"T.\u00a0Schneider, M.\u00a0Zoher, GMW vs. Yao? Efficient secure two-party computation with low depth circuits, in FC (2013)","DOI":"10.1007\/978-3-642-39884-1_23"},{"key":"9472_CR38","doi-asserted-by":"crossref","unstructured":"E.M. Songhori, S.U. Hussain, A.\u00a0Sadeghi, T.\u00a0Schneider, F.\u00a0Koushanfar, TinyGarble: Highly compressed and scalable sequential garbled circuits, in S &P (2015)","DOI":"10.1109\/SP.2015.32"},{"key":"9472_CR39","doi-asserted-by":"crossref","unstructured":"A.C. Yao, How to generate and exchange secrets, in FOCS (1986)","DOI":"10.1109\/SFCS.1986.25"},{"key":"9472_CR40","unstructured":"S.\u00a0Zahur, D.\u00a0Evans, Obliv-C: A language for extensible data-oblivious computation. Cryptology ePrint Archive 1153 (2015)"},{"key":"9472_CR41","doi-asserted-by":"crossref","unstructured":"S.\u00a0Zahur, M.\u00a0Rosulek, D.\u00a0Evans, Two halves make a whole\u2014Reducing data transfer in garbled circuits using half gates, in EUROCRYPT (2015)","DOI":"10.1007\/978-3-662-46803-6_8"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09472-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09472-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09472-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:02:49Z","timestamp":1698163369000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09472-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,3]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["9472"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09472-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,3]]},"assertion":[{"value":"22 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"34"}}