1 Search Results for "Badrinarayanan, Saikrishna"

Document

DOI: 10.4230/LIPIcs.ITC.2022.10

Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

Authors: Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs

Published in: LIPIcs, Volume 230, 3rd Conference on Information-Theoretic Cryptography (ITC 2022)

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

Cite as

Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, and Daniel Wichs. Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{badrinarayanan_et_al:LIPIcs.ITC.2022.10,
  author =	{Badrinarayanan, Saikrishna and Ishai, Yuval and Khurana, Dakshita and Sahai, Amit and Wichs, Daniel},
  title =	{{Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC}},
  booktitle =	{3rd Conference on Information-Theoretic Cryptography (ITC 2022)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-238-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{230},
  editor =	{Dachman-Soled, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2022.10},
  URN =		{urn:nbn:de:0030-drops-164885},
  doi =		{10.4230/LIPIcs.ITC.2022.10},
  annote =	{Keywords: XOR Lemma, Resettable MPC, Obfuscation}
}

Refine by Author
1 Badrinarayanan, Saikrishna
1 Ishai, Yuval
1 Khurana, Dakshita
1 Sahai, Amit
1 Wichs, Daniel

Refine by Classification
1 Theory of computation → Computational complexity and cryptography
1 Theory of computation → Cryptographic protocols

Refine by Keyword
1 Obfuscation
1 Resettable MPC
1 XOR Lemma

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Badrinarayanan, Saikrishna"

Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

Abstract

Cite as

Thanks for your feedback!

Could not send message