On the security of the “Free-XOR” technique. (English) Zbl 1303.94075

Cramer, Ronald (ed.), Theory of cryptography. 9th theory of cryptography conference, TCC 2012, Taormina, Sicily, Italy, March 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-28913-2/pbk). Lecture Notes in Computer Science 7194, 39-53 (2012).
Summary: A. Yao’s garbled-circuit approach enables constant-round secure two-party computation of any function [How to generate and exchange secrets, IEEE 27th Ann. Symp. FOCS 1986, 162–167 (1986)]. In Yao’s original construction, each gate in the circuit requires the parties to perform a constant number of encryptions/decryptions and to send/receive a constant number of ciphertexts. V. Kolesnikov and T. Schneider [ICALP 2008, Lect. Notes Comput. Sci. 5126, 486–498 (2008; Zbl 1155.94374)] proposed an improvement that allows XOR gates to be evaluated “for free,” incurring no cryptographic operations and zero communication. Their “free-XOR” technique has proven very popular, and has been shown to improve performance of garbled-circuit protocols by up to a factor of 4.
Kolesnikov and Schneider proved security of their approach in the random oracle model, and claimed that (an unspecified variant of) correlation robustness suffices; this claim has been repeated in subsequent work, and similar ideas have since been used in other contexts. We show that the free-XOR technique cannot be proven secure based on correlation robustness alone; somewhat surprisingly, some form of circular security is also required. We propose an appropriate definition of security for hash functions capturing the necessary requirements, and prove security of the free-XOR approach when instantiated with any hash function satisfying our definition.
Our results do not impact the security of the free-XOR technique in practice, or imply an error in the free-XOR work, but instead pin down the assumptions needed to prove security.
For the entire collection see [Zbl 1238.94002].


94A60 Cryptography
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)


Zbl 1155.94374
Full Text: DOI