[Resource Topic] 2023/1088: Building Hard Problems by Combining Easy Ones

Welcome to the resource topic for 2023/1088

Building Hard Problems by Combining Easy Ones

Authors: Riddhi Ghosal, Amit Sahai


In this work, we initiate a new conceptual line of attack on the fundamental question of how to generate hard problems. Motivated by the need for one-way functions in cryptography, we propose an information-theoretic framework to study the question of generating new provably hard one-way functions by composing functions that are easy to invert and evaluate, where each such easy function is modeled as a random oracles paired with another oracle that implements an inverse function.

ePrint: https://eprint.iacr.org/2023/1088

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .