Improved garbled circuit: Free XOR gates and applications. (English) Zbl 1155.94374

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-70582-6/pbk). Lecture Notes in Computer Science 5126, 486-498 (2008).
Summary: We present a new garbled circuit construction for two-party secure function evaluation (SFE). In our one-round protocol, XOR gates are evaluated “for free”, which results in the corresponding improvement over the best garbled circuit implementations (e.g. Fairplay).
We build permutation networks and Universal Circuits (UC) almost exclusively of XOR gates; this results in a factor of up to 4 improvement (in both computation and communication) of their SFE. We also improve integer addition and equality testing by factor of up to 2.
We rely on the Random Oracle (RO) assumption. Our constructions are proven secure in the semi-honest model.
For the entire collection see [Zbl 1141.68001].


94A60 Cryptography
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI Link