[Resource Topic] 2023/1091: On Derandomizing Yao's Weak-to-Strong OWF Construction

Welcome to the resource topic for 2023/1091

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

Authors: Chris Brzuska, Geoffroy Couteau, Pihla Karanko, Felix Rohrbach


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-\tfrac{1}{p(n)}, yields a strong OWF g, showing that weak and strong OWFs are black-box equivalent. Yao’s transformation 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.

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 g from a weak OWF f, which can be inverted with probability 1-\tfrac{1}{p(n)}, the input size of g must grow as \Omega(p(n)). Here, direct product refers to the following structure: the construction g executes some arbitrary pre-processing function (independent of f) on its input s, obtaining a vector (x_1, \cdots, x_l), and outputs f(x_1), \cdots, f(x_l). When setting the pre-processing to be the identity, one recovers thus Yao’s construction.

Our result generalizes to functions g 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 f 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.

ePrint: https://eprint.iacr.org/2023/1091

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .