Document Open Access Logo

Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC

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

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.10.pdf
  • Filesize: 0.71 MB
  • 21 pages

Document Identifiers

Author Details

Saikrishna Badrinarayanan
  • Snap, Mountain View, USA
Yuval Ishai
  • Technion, Haifa, Israel
Dakshita Khurana
  • University of Illinois, Urbana-Champaign, IL, USA
Amit Sahai
  • University of California Los Angeles, CA, USA
  • Center for Encrypted Functionalities, Los Angeles, CA, USA
Daniel Wichs
  • Northeastern University, Boston, MA, USA
  • NTT Research, Sunnyvale, CA, USA

Funding

  • Badrinarayanan, Saikrishna: Work done while at UCLA.
  • Ishai, Yuval: Supported in part by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20.
  • Khurana, Dakshita: Supported in part by DARPA SIEVE project contract No. #HR00112020024, a gift from Visa Research, and a C3AI DTI award.
  • Sahai, Amit: Supported in part from a Simons Investigator Award, DARPA SIEVE award, NTT Research, NSF Frontier Award 1413955, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, and an Okawa Foundation Research Grant. This material is based upon work supported by the Defense Advanced Research Projects Agency through Award HR00112020024.
  • Wichs, Daniel: Partially supported by NSF grants CNS-1750795, CNS- 2055510 and the Alfred P. Sloan Research Fellowship.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ITC.2022.10

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Cryptographic protocols
Keywords
  • XOR Lemma
  • Resettable MPC
  • Obfuscation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shweta Agrawal. Indistinguishability obfuscation without multilinear maps: New methods for bootstrapping and instantiation. In EUROCRYPT, 2019. Google Scholar
  2. Shweta Agrawal and Alice Pellet-Mary. Indistinguishability obfuscation without maps: Attacks and fixes for noisy linear FE. In EUROCRYPT, 2020. Google Scholar
  3. William Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In EUROCRYPT, 2001. Google Scholar
  4. Navid Alamati and Chris Peikert. Three’s compromised too: Circular insecurity for any cycle length from (ring-)lwe. In CRYPTO, 2016. Google Scholar
  5. Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry. Differing-inputs obfuscation and applications. IACR Cryptology ePrint Archive, 2013. URL: http://eprint.iacr.org/2013/689.
  6. Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. Indistinguishability obfuscation without multilinear maps: New paradigms via low degree weak pseudorandomness and security amplification. In CRYPTO, 2019. Google Scholar
  7. Prabhanjan Ananth, Aayush Jain, Moni Naor, Amit Sahai, and Eylon Yogev. Universal constructions and robust combiners for indistinguishability obfuscation and witness encryption. In CRYPTO, 2016. Google Scholar
  8. Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold FHE. In EUROCRYPT, 2012. Google Scholar
  9. Saikrishna Badrinarayanan, Sanjam Garg, Yuval Ishai, Amit Sahai, and Akshay Wadia. Two-message witness indistinguishability and secure computation in the plain model from new assumptions. In ASIACRYPT, 2017. Google Scholar
  10. Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Dakshita Khurana, and Amit Sahai. Round optimal concurrent MPC via strong simulation. In TCC, 2017. Google Scholar
  11. Boaz Barak, Oded Goldreich, Shafi Goldwasser, and Yehuda Lindell. Resettably-sound zero-knowledge and its applications. FOCS, 2001. Google Scholar
  12. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In CRYPTO, 2001. Google Scholar
  13. Boaz Barak and Amit Sahai. How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In FOCS, 2005. Google Scholar
  14. Mihir Bellare, Dennis Hofheinz, and Scott Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening. In EUROCRYPT, 2009. Google Scholar
  15. Mihir Bellare, Russell Impagliazzo, and Moni Naor. Does parallel repetition lower the error in computationally sound protocols? In FOCS, 1997. Google Scholar
  16. Mihir Bellare, Thomas Ristenpart, and Stefano Tessaro. Multi-instance security and its application to password-based cryptography. In CRYPTO, 2012. Google Scholar
  17. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In CCS, 1993. Google Scholar
  18. Eli Biham, Yaron J. Goren, and Yuval Ishai. Basing weak public-key cryptography on strong one-way functions. In TCC, 2008. Google Scholar
  19. Nir Bitansky and Huijia Lin. One-message zero knowledge and non-malleable commitments. In TCC, 2018. Google Scholar
  20. Nir Bitansky and Omer Paneth. On the impossibility of approximate obfuscation and applications to resettable cryptography. In STOC, 2013. Google Scholar
  21. Nir Bitansky and Omer Paneth. On non-black-box simulation and the impossibility of approximate obfuscation. SIAM J. Comput., 2015. Google Scholar
  22. Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability obfuscation. In Yehuda Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 52-73. Springer, Heidelberg, February 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_3.
  23. Zvika Brakerski and Nico Döttling. Two-message statistically sender-private OT from LWE. In TCC 2018, 2018. Google Scholar
  24. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Candidate io from homomorphic encryption schemes. In EUROCRYPT, 2020. Google Scholar
  25. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and pairings are not necessary for io: Circular-secure LWE suffices. IACR Cryptol. ePrint Arch., 2020. URL: https://eprint.iacr.org/2020/1024.
  26. Christina Brzuska, Pooya Farshim, and Arno Mittelbach. Indistinguishability obfuscation and uces: The case of computationally unpredictable sources. In CRYPTO, 2014. Google Scholar
  27. Ran Canetti, Oded Goldreich, Shafi Goldwasser, and Silvio Micali. Resettable zero-knowledge (extended abstract). In STOC, 2000. Google Scholar
  28. Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, Muthuramakrishnan Venkitasubramaniam, and Ivan Visconti. 4-round resettably-sound zero knowledge. In TCC, 2014. Google Scholar
  29. Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, and Ivan Visconti. Simultaneous resettability from one-way functions. In FOCS, 2013. Google Scholar
  30. Kai-Min Chung, Rafael Pass, and Karn Seth. Non-black-box simulation from one-way functions and applications to resettable security. SIAM J. Comput., 2016. Google Scholar
  31. Lalita Devadas, Willy Quach, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs. Succinct LWE sampling, random polynomials, and obfuscation. In Kobbi Nissim and Brent Waters, editors, Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II, volume 13043 of Lecture Notes in Computer Science, pages 256-287. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-90453-1_9.
  32. Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing cracks in the concrete: Random oracles with auxiliary input, revisited. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology - EUROCRYPT 2017, Part II, volume 10211 of Lecture Notes in Computer Science, pages 473-495. Springer, Heidelberg, April / May 2017. URL: https://doi.org/10.1007/978-3-319-56614-6_16.
  33. Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. Spooky encryption and its applications. In CRYPTO, 2016. Google Scholar
  34. Yevgeniy Dodis, Abhishek Jain, Tal Moran, and Daniel Wichs. Counterexamples to hardness amplification beyond negligible. In Ronald Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science, pages 476-493. Springer, Heidelberg, March 2012. URL: https://doi.org/10.1007/978-3-642-28914-9_27.
  35. Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky. Trapdoor hash functions and their applications. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019, Part III, volume 11694 of Lecture Notes in Computer Science, pages 3-32. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_1.
  36. Uriel Feige. On the success probability of the two provers in one-round proof systems. In Structure in Complexity Theory Conference. IEEE Computer Society, 1991. Google Scholar
  37. Lance Fortnow. The complexity of perfect zero-knowledge. Advances in Computing Research, 1989. Google Scholar
  38. Sanjam Garg, Craig Gentry, Shai Halevi, and Mariana Raykova. Two-round secure MPC from indistinguishability obfuscation. In TCC, 2014. Google Scholar
  39. Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. In CRYPTO, 2014. Google Scholar
  40. Romain Gay, Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from simple-to-state hard problems: New assumptions, new techniques, and simplification. In EUROCRYPT, 2021. Google Scholar
  41. Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. In STOC, 2021. Google Scholar
  42. Craig Gentry, Shai Halevi, Mariana Raykova, and Daniel Wichs. Outsourcing private RAM computation. In FOCS, 2014. Google Scholar
  43. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In STOC, 1989. Google Scholar
  44. Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao’s XOR-Lemma, pages 273-301. Springer Berlin Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_23.
  45. Rishab Goyal, Venkata Koppula, and Brent Waters. Lockable obfuscation. In FOCS, 2017. Google Scholar
  46. Rishab Goyal, Venkata Koppula, and Brent Waters. Separating semantic and circular security for symmetric-key bit encryption from the learning with errors assumption. In EUROCRYPT, 2017. Google Scholar
  47. Vipul Goyal and Hemanta K. Maji. Stateless cryptographic protocols. In FOCS, 2011. Google Scholar
  48. Vipul Goyal and Amit Sahai. Resettably secure computation. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, volume 5479 of Lecture Notes in Computer Science, pages 54-71. Springer, Heidelberg, April 2009. URL: https://doi.org/10.1007/978-3-642-01001-9_3.
  49. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In FOCS, 2018. Google Scholar
  50. Satoshi Hada. Zero-knowledge and code obfuscation. In ASIACRYPT, 2000. Google Scholar
  51. Shai Halevi and Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. J. Cryptol., 2012. Google Scholar
  52. Dennis Hofheinz, Vanishree Rao, and Daniel Wichs. Standard security does not imply indistinguishability under selective opening. In TCC, 2016. Google Scholar
  53. Dennis Hofheinz and Andy Rupp. Standard versus selective opening security: Separation and equivalence results. In TCC, 2014. Google Scholar
  54. Justin Holmgren and Lisa Yang. The parallel repetition of non-signaling games: counterexamples and dichotomy. In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing, pages 185-192. ACM Press, June 2019. URL: https://doi.org/10.1145/3313276.3316367.
  55. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In FOCS, 1995. Google Scholar
  56. Yuval Ishai, Omkant Pandey, and Amit Sahai. Public-coin differing-inputs obfuscation and its applications. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part II, volume 9015 of Lecture Notes in Computer Science, pages 668-697. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46497-7_26.
  57. Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. How to leverage hardness of constant-degree expanding polynomials over r to build io. In EUROCRYPT, 2019. Google Scholar
  58. Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In STOC, 2021. Google Scholar
  59. Abhishek Jain and Krzysztof Pietrzak. Parallel repetition for leakage resilience amplification revisited. In TCC, 2011. Google Scholar
  60. Dakshita Khurana and Amit Sahai. How to achieve non-malleability in one or two rounds. In FOCS, 2017. Google Scholar
  61. Venkata Koppula, Kim Ramchen, and Brent Waters. Separations in circular security for arbitrary length key cycles. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015: 12th Theory of Cryptography Conference, Part II, volume 9015 of Lecture Notes in Computer Science, pages 378-400. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46497-7_15.
  62. Venkata Koppula and Brent Waters. Circular security separations for arbitrary length cycles from LWE. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 681-700. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_24.
  63. Leonid A. Levin. One-way functions and pseudorandom generators. In STOC, 1985. Google Scholar
  64. Allison B. Lewko and Brent Waters. On the insecurity of parallel repetition for leakage resilience. In 51st Annual Symposium on Foundations of Computer Science, pages 521-530. IEEE Computer Society Press, October 2010. URL: https://doi.org/10.1109/FOCS.2010.57.
  65. Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In SODA, 2001. Google Scholar
  66. Rafael Pass. Simulation in quasi-polynomial time, and its application to protocol composition. In EUROCRYPT, 2003. Google Scholar
  67. Krzysztof Pietrzak and Douglas Wikström. Parallel repetition of computationally sound protocols revisited. In TCC, 2007. Google Scholar
  68. Manoj Prabhakaran and Amit Sahai. New notions of security: achieving universal composability without trusted setup. In László Babai, editor, STOC, 2004. Google Scholar
  69. Ron Rothblum. On the circular security of bit-encryption. In Amit Sahai, editor, TCC 2013: 10th Theory of Cryptography Conference, volume 7785 of Lecture Notes in Computer Science, pages 579-598. Springer, Heidelberg, March 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_32.
  70. Ronen Shaltiel. Is it possible to improve yao’s XOR lemma using reductions that exploit the efficiency of their oracle? In APPROX/RANDOM, 2020. Google Scholar
  71. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM J. Comput., 2010. Google Scholar
  72. Victor Shoup. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, 1997. Google Scholar
  73. Dominique Unruh. Random oracles and auxiliary input. In CRYPTO, 2007. Google Scholar
  74. Hoeteck Wee and Daniel Wichs. Candidate obfuscation via oblivious LWE sampling. In EUROCRYPT, 2021. Google Scholar
  75. Daniel Wichs and Giorgos Zirdelis. Obfuscating compute-and-compare programs under LWE. In Chris Umans, editor, 58th Annual Symposium on Foundations of Computer Science, pages 600-611. IEEE Computer Society Press, October 2017. URL: https://doi.org/10.1109/FOCS.2017.61.
  76. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In FOCS, 1982. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact