Paper 2023/1091

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

Chris Brzuska, Aalto University
Geoffroy Couteau, CNRS, IRIF, Université Paris Cité
Pihla Karanko, Aalto University
Felix Rohrbach, TU Darmstadt

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.

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

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2021
one-way functionweak OWForacle separation
Contact author(s)
chris brzuska @ aalto fi
geoffroy couteau @ ens fr
pihla karanko @ aalto fi
felix rohrbach @ cryptoplexity de
2023-07-16: approved
2023-07-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Brzuska and Geoffroy Couteau and Pihla Karanko and Felix Rohrbach},
      title = {On Derandomizing Yao's Weak-to-Strong OWF Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1091},
      year = {2023},
      doi = {10.1007/978-3-030-90453-1_15},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.