On Derandomizing Yao’s Weak-to-Strong OWF Construction

The celebrated result of Yao (Yao, FOCS’82) shows that concatenating \(n\cdot p(n)\) copies of a weak one-way function (OWF) f, which can be inverted with probability \(1-\tfrac{1}{p(n)}\), suffices to construct a strong OWF g, showing that weak and strong OWFs are black-box equivalent. This direct product theorem for hardness amplification of OWFs has been very influential. However, the construction of Yao is not security-preserving, i.e., the input to g needs to be much larger than the input to f. Understanding whether a larger input is inherent is a long-standing open question.