Welcome to the resource topic for 2023/1091
Title:
On Derandomizing Yao’s Weak-to-Strong OWF Construction
Authors: Chris Brzuska, Geoffroy Couteau, Pihla Karanko, Felix Rohrbach
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-\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 .