TU Darmstadt / ULB / TUbiblio

Breaking and Fixing Garbled Circuits When a Gate has Duplicate Input Wires

Nieminen, Raine ; Schneider, Thomas
ed.: 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
Article, Bibliographie

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.

Item Type: Article
Erschienen: 2023
Creators: Nieminen, Raine ; Schneider, Thomas
Type of entry: Bibliographie
Title: Breaking and Fixing Garbled Circuits When a Gate has Duplicate Input Wires
Language: English
Date: 3 August 2023
Publisher: Springer
Journal or Publication Title: Journal of Cryptology
Volume of the journal: 36
Issue Number: 34
DOI: 10.1007/s00145-023-09472-4
URL / URN: https://link.springer.com/article/10.1007/s00145-023-09472-4
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.

Uncontrolled Keywords: Engineering, E4, CYSEC, GRK Privacy&Trust for Mobile Users (Project A.1)
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)
20 Department of Computer Science > Kryptographische Protokolle
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Graduiertenkollegs
DFG-Graduiertenkollegs > Research Training Group 2050 Privacy and Trust for Mobile Users
Profile Areas
Profile Areas > Cybersecurity (CYSEC)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Date Deposited: 28 Sep 2023 13:42
Last Modified: 28 Sep 2023 13:42
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details