Abstract

The celebrated result of Yao (Yao, FOCS’82) shows that concatenating n⋅p(n) copies of a weak one-way function (OWF) f, which can be inverted with probability 1−1p(n), suffices to construct a strong OWF g, showing that weak and strong OWFs are black-box equivalent. This direct product theorem for hardness amplification of OWFs has been very influential. However, the construction of Yao 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−1p(n), the input size of g must grow as Ω(p(n)). By direct product construction, we refer to any construction with the following structure: the construction g executes some arbitrary pre-processing function (independent of f) on its input, obtaining a vector (y1,⋯,yl), and outputs f(y1),⋯,f(yl). Note that Yao’s construction is obtained by setting the pre-processing to be the identity. 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 of having a very lossy post-processing of the outputs of f).

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.
Original languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part II
EditorsKobbi Nissim, Brent Waters, Brent Waters
PublisherSpringer
Pages429-456
Number of pages28
ISBN (Electronic)978-3-030-90453-1
ISBN (Print)9783030904524
DOIs
Publication statusPublished - 4 Nov 2021
MoE publication typeA4 Conference publication
EventTheory of Cryptography Conference - Raleigh, United States
Duration: 8 Nov 202111 Nov 2021
Conference number: 19

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13043
ISSN (Print)0302-9743

Conference

ConferenceTheory of Cryptography Conference
Abbreviated titleTCC
Country/TerritoryUnited States
CityRaleigh
Period08/11/202111/11/2021

Fingerprint

Dive into the research topics of 'On Derandomizing Yao’s Weak-to-Strong OWF Construction'. Together they form a unique fingerprint.

Cite this