Paper 2023/1091
On Derandomizing Yao's WeaktoStrong OWF Construction
Abstract
The celebrated result of Yao (FOCS'82) shows that concatenating $n\cdot p(n)$ copies of a weak oneway 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 blackbox equivalent. Yao's transformation is not securitypreserving, 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 longstanding 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 preprocessing 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 preprocessing to be the identity, one recovers thus Yao's construction. Our result generalizes to functions $g$ with postprocessing, as long as the postprocessing function is not too lossy. Thus, in essence, any weaktostrong OWF hardness amplification must either (1) be very far from securitypreserving, (2) use adaptivity, or (3) must be very far from a directproduct structure (in the sense that postprocessing of the outputs of $f$ is very lossy). On a technical level, we use ideas from lower bounds for secretsharing to prove the impossibility of derandomizing Yao in a blackbox 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
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in TCC 2021
 DOI
 10.1007/9783030904531_15
 Keywords
 oneway functionweak OWForacle separation
 Contact author(s)

chris brzuska @ aalto fi
geoffroy couteau @ ens fr
pihla karanko @ aalto fi
felix rohrbach @ cryptoplexity de  History
 20230716: approved
 20230713: received
 See all versions
 Short URL
 https://ia.cr/2023/1091
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1091, author = {Chris Brzuska and Geoffroy Couteau and Pihla Karanko and Felix Rohrbach}, title = {On Derandomizing Yao's WeaktoStrong OWF Construction}, howpublished = {Cryptology ePrint Archive, Paper 2023/1091}, year = {2023}, doi = {10.1007/9783030904531_15}, note = {\url{https://eprint.iacr.org/2023/1091}}, url = {https://eprint.iacr.org/2023/1091} }