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 = \varOmega (\log ^{1+\varepsilon }n)\) for all \(\varepsilon > 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 \(\epsilon \) -close to the binomial distribution.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Adding Two Easy Functions Is Always Hard to Invert

  • Hayato Gibo,
  • Yohei Watanabe,
  • Mitsugu Iwamoto

摘要

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 = \varOmega (\log ^{1+\varepsilon }n)\) for all \(\varepsilon > 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 \(\epsilon \) -close to the binomial distribution.