Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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: 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. 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.

Original languageEnglish (US)
Title of host publication3rd Conference on Information-Theoretic Cryptography, ITC 2022
EditorsDana Dachman-Soled
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772389
StatePublished - Jul 1 2022
Event3rd Conference on Information-Theoretic Cryptography, ITC 2022 - Cambridge, United States
Duration: Jul 5 2022Jul 7 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference3rd Conference on Information-Theoretic Cryptography, ITC 2022
Country/TerritoryUnited States


  • Obfuscation
  • Resettable MPC
  • XOR Lemma

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC'. Together they form a unique fingerprint.

Cite this