Building Hard Problems by Combining Easy Ones: Revisited

Yael Eisenberg; Christopher Havens; Alexis Korb; Amit Sahai

Paper 2025/223

Building Hard Problems by Combining Easy Ones: Revisited

Yael Eisenberg

Christopher Havens, University of California, Los Angeles

Alexis Korb

, University of California, Los Angeles

Amit Sahai

, University of California, Los Angeles

Abstract

We establish the following theorem: Let be random functions from to , . For all polynomial-query-bounded distinguishers making at most queries to each oracle, there exists a poly-time oracle simulator and a constant such that the probability is negligible, that is

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: random oracle simulator
Contact author(s): ye45 @ cornell edu
chavens28 @ gmail com
alexiskorb @ cs ucla edu
sahai @ cs ucla edu
History: 2025-02-14: approved; 2025-02-13: received; See all versions
Short URL: https://ia.cr/2025/223
License: CC BY

BibTeX

@misc{cryptoeprint:2025/223,
      author = {Yael Eisenberg and Christopher Havens and Alexis Korb and Amit Sahai},
      title = {Building Hard Problems by Combining Easy Ones: Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/223},
      year = {2025},
      url = {https://eprint.iacr.org/2025/223}
}