Paper 2025/223
Building Hard Problems by Combining Easy Ones: Revisited
, University of California, Los Angeles, University of California, Los AngelesAbstract
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
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}
}
