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.
OtsikkoTheory of Cryptography
Alaotsikko19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part II
ToimittajatKobbi Nissim, Brent Waters, Brent Waters
ISBN (elektroninen)978-3-030-90453-1
ISBN (painettu)9783030904524
DOI - pysyväislinkit
TilaJulkaistu - 4 marrask. 2021
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaTheory of Cryptography Conference - Raleigh, Yhdysvallat
Kesto: 8 marrask. 202111 marrask. 2021
Konferenssinumero: 19


NimiLecture Notes in Computer Science
ISSN (painettu)0302-9743


ConferenceTheory of Cryptography Conference


Sukella tutkimusaiheisiin 'On Derandomizing Yao’s Weak-to-Strong OWF Construction'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä