Building Hard Problems by Combining Easy Ones: Revisited

Yael Eisenberg; Christopher Havens; Alexis Korb; Elio Merolle; 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

Elio Merolle, University of California, Los Angeles

Amit Sahai

, University of California, Los Angeles

Abstract

We establish the following theorem: Let $\mathsf{O}_0, \mathsf{O}_1, \mathsf{R}$ be random functions from $\{0,1\}^n$ to $\{0,1\}^n$, $n \in \mathbb{N}$. For all polynomial-query-bounded distinguishers $\mathsf{D}$ making at most $q=\mathsf{poly}(n)$ queries to each oracle, there exists a poly-time oracle simulator $\mathsf{Sim}^{(\cdot)}$ and a constant $c>0$ such that the probability is negligible, that is $$\left|\Pr\left[{\mathsf{D}^{(\mathsf{O}_0+\mathsf{O}_1),(\mathsf{O}_0,\mathsf{O}_1,\mathsf{O}_0^{-1},\mathsf{O}_1^{-1})}(1^n)=1}\right]-\Pr\left[{\mathsf{D}^{\mathsf{R},\mathsf{Sim}^\mathsf{R}}(1^n)=1}\right]\right| = negl(n).$$

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
eliom @ g ucla edu
sahai @ cs ucla edu
History: 2025-12-05: revised; 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 Elio Merolle 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}
}