## 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.

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 language | English |
---|---|

Title of host publication | Theory of Cryptography |

Subtitle of host publication | 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part II |

Editors | Kobbi Nissim, Brent Waters, Brent Waters |

Publisher | Springer |

Pages | 429-456 |

Number of pages | 28 |

ISBN (Electronic) | 978-3-030-90453-1 |

ISBN (Print) | 9783030904524 |

DOIs | |

Publication status | Published - 4 Nov 2021 |

MoE publication type | A4 Conference publication |

Event | Theory of Cryptography Conference - Raleigh, United States Duration: 8 Nov 2021 → 11 Nov 2021 Conference number: 19 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 13043 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | Theory of Cryptography Conference |
---|---|

Abbreviated title | TCC |

Country/Territory | United States |

City | Raleigh |

Period | 08/11/2021 → 11/11/2021 |