Paper 2023/1091

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

Abstract

The celebrated result of 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-\frac{1}{p(n)}$, yields a strong OWF $$, showing that weak and strong OWFs are black-box equivalent. Yao's transformation is not security-preserving, i.e., the input to $$ needs to be much larger than the input to $$. Understanding whether a larger input is inherent is a long-standing open question. In this work, we explore necessary features of constructions which achieve short input length by proving the following: for any direct product construction of a strong OWF $$ from a weak OWF $$, which can be inverted with probability $$, the input size of $$ must grow as $$. Here, direct product refers to the following structure: the construction $$ executes some arbitrary pre-processing function (independent of $$) on its input $$, obtaining a vector $$, and outputs $$. When setting the pre-processing to be the identity, one recovers thus Yao's construction. Our result generalizes to functions $$ with post-processing, as long as the post-processing function is not too lossy. Thus, in essence, any weak-to-strong OWF hardness amplification must either (1) be very far from security-preserving, (2) use adaptivity, or (3) must be very far from a direct-product structure (in the sense that post-processing of the outputs of $$ is very lossy). On a technical level, we use ideas from lower bounds for secret-sharing to prove the impossibility of derandomizing Yao in a black-box way. Our results are in line with Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (FOCS 1990) who derandomize Yao's construction for regular weak OWFs by evaluating the OWF along a random walk on an expander graph – the construction is adaptive, since it alternates steps on the expander graph with evaluations of the weak OWF.

Note: This version strengthens the main theorem of the 2021 TCC paper slightly (arbitrary constant instead of a fixed constant) and improves the overall presentation