Paper 2025/223 Original: eprint.iacr.org/2025/223 ↗

Building Hard Problems by Combining Easy Ones: Revisited

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).$$