Publications

One-way functions play a fundamental role in the theory of cryptography; however, proving their existence remains a long-standing open problem. Ghosal and Sahai proposed a novel information-theoretic framework for constructing a one-way function by combining two easy functions, each modeled as a random oracle paired with its inverse oracle, both of which are accessible to the distinguisher. They demonstrated that the resulting function f is hard to invert in the sense of indifferentiability, assuming that the gap between output and input lengths satisfies m-n = Ω(log^{1+ε}n) for all ε > 0. However, this condition is somewhat artificial, and their claim that combining easy functions yields hardness holds only under this restricted -- prompting the natural question of whether such a constraint can be eliminated. In this work, we answer this question affirmatively: the condition is not necessary. We prove that adding two easy functions always results in a one-way function, regardless of the gap between m and n. Our proof relies on a careful simulation of the inverse oracle using a polynomial-time sampling algorithm in n that generates outputs ϵ -close to the binomial distribution.