Welcome to the resource topic for 2022/901
Title:
Garbled-Circuits from an SCA Perspective: Free XOR can be Quite Expensive. . .
Authors: Itamar Levi and Carmit Hazay
Abstract:Garbling schemes, invented in the 80’s by Yao (FOCS’86), have been a versatile and fundamental tool in modern cryptography. A prominent application of garbled circuits is constant round secure two-party computation, led to a long line of study of this object, where one of the most influential optimizations is Free-XOR (Kolesnikov and Schneider ICALP’08), introducing a global offset \Delta for all garbled wire values where XOR gates are computed directly without garbling them. To date, garbling sachems were not studied per their side-channel attacks (SCA) security characteristics, even though SCA pose a significant security threat to cryptographic devices. In this research we demonstrate that adversaries utilizing advanced SCA tools such as horizontal attacks, mixed with advanced hypothesis building and standard (vertical) SCA tools, can jeopardize garbling implementations. Our main observation is that garbling schemes utilizing a global secret \Delta open a door to quite trivial side-channel attacks. We model our side-channel attacks on the garbler’s device and discuss the asymmetric setting where various computations are not performed on the evaluator side. This enables dangerous leakage extraction on the garbler and renders our attack impossible on the evaluator’s side. Theoretically, we first demonstrate on a simulated environment, that such attacks are quite devastating. Concretely, our attack is capable of extracting \Delta when the circuit embeds only 8 input non-linear gates with fifth/first-order attack Success-Rates of 0.65/0.7. With as little as 3 such gates, our attack reduces the first-order Guessing Entropy of \Delta from 128 to \sim48-bits. We further demonstrate our attack via an implementation and measurements data over an STM 32-bit processor software implementing circuit garbling, and discuss their limitations and mitigation tactics on logical, protocol and implementation layers.
ePrint: https://eprint.iacr.org/2022/901
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .