### Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

##### Abstract

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)
Category
Foundations
Publication info
Published elsewhere. ITC 2022
Keywords
obfuscation MPC XOR Lemma
Contact author(s)
bsaikrishna7393 @ gmail com
yuval ishai @ gmail com
dakshkhurana @ gmail com
amitsahai @ gmail com
danwichs @ gmail com
History
2022-05-31: approved
See all versions
Short URL
https://ia.cr/2022/681

CC BY

BibTeX

@misc{cryptoeprint:2022/681,
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{https://eprint.iacr.org/2022/681}},
url = {https://eprint.iacr.org/2022/681}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.