Nieminen, Raine ; Schneider, Thomas
Hrsg.: Springer (2023)
Breaking and Fixing Garbled Circuits When a Gate has Duplicate Input Wires.
In: Journal of Cryptology, 36 (34)
doi: 10.1007/s00145-023-09472-4
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
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 (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler (USENIX Security’04), 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.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2023 |
| Autor(en): | Nieminen, Raine ; Schneider, Thomas |
| Art des Eintrags: | Bibliographie |
| Titel: | Breaking and Fixing Garbled Circuits When a Gate has Duplicate Input Wires |
| Sprache: | Englisch |
| Publikationsjahr: | 3 August 2023 |
| Verlag: | Springer |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Journal of Cryptology |
| Jahrgang/Volume einer Zeitschrift: | 36 |
| (Heft-)Nummer: | 34 |
| DOI: | 10.1007/s00145-023-09472-4 |
| URL / URN: | https://link.springer.com/article/10.1007/s00145-023-09472-4 |
| Kurzbeschreibung (Abstract): | 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 (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler (USENIX Security’04), 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. |
| Freie Schlagworte: | Engineering, E4, CYSEC, GRK Privacy&Trust for Mobile Users (Project A.1) |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Praktische Kryptographie und Privatheit 20 Fachbereich Informatik > Kryptographische Protokolle DFG-Sonderforschungsbereiche (inkl. Transregio) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche DFG-Graduiertenkollegs DFG-Graduiertenkollegs > Graduiertenkolleg 2050 Privacy and Trust for Mobile Users Profilbereiche Profilbereiche > Cybersicherheit (CYSEC) DFG-Sonderforschungsbereiche (inkl. Transregio) > Sonderforschungsbereiche > SFB 1119: CROSSING – Kryptographiebasierte Sicherheitslösungen als Grundlage für Vertrauen in heutigen und zukünftigen IT-Systemen |
| Hinterlegungsdatum: | 28 Sep 2023 13:42 |
| Letzte Änderung: | 28 Sep 2023 13:42 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum