Paper 2022/681

Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

Saikrishna Badrinarayanan, Snap
Yuval Ishai, Technion
Dakshita Khurana, University of Illinois, Urbana-Champaign
Amit Sahai, UCLA and Center for Encrypted Functionalities
Daniel Wichs, Northeastern University and NTT Research

We provide counterexamples to the ``dream'' version of Yao's XOR Lemma. In particular, we put forward explicit candidates for hard predicates, such that the advantage of predicting the XOR of many independent copies does not decrease beyond some fixed negligible function, even as the number of copies gets arbitrarily large. We provide two such constructions: 1) Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete class of circuits). It develops a general framework that may be of broader interest, and allows us to embed an instance of a resettably-secure multiparty computation protocol into a one-way function. Along the way, we design the first resettably-secure multiparty computation protocol for general functionalities in the plain model with super-polynomial simulation, under standard assumptions. 2) The second construction relies on public-coin differing-inputs obfuscation (PCdiO) along with a certain form of hash-function security called extended second-preimage resistance (ESPR). It starts with a previously known counterexample to the dream direct-product hardness amplification based on ESPR, and uses PCdiO to upgrade it into a counterexample for the XOR lemma. Prior to our work, even completely heuristic counterexamples of this type were not known.

Available format(s)
Publication info
Published elsewhere. ITC 2022
obfuscation MPC XOR Lemma
Contact author(s)
bsaikrishna7393 @ gmail com
yuval ishai @ gmail com
dakshkhurana @ gmail com
amitsahai @ gmail com
danwichs @ gmail com
2022-05-31: approved
2022-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Saikrishna Badrinarayanan and Yuval Ishai and Dakshita Khurana and Amit Sahai and Daniel Wichs},
      title = {Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2022/681},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.