Building Hard Problems by Combining Easy Ones
- Resource Type
- Conference
- Authors
- Ghosal, Riddhi; Sahai, Amit
- Source
- 2023 IEEE International Symposium on Information Theory (ISIT) Information Theory (ISIT), 2023 IEEE International Symposium on. :1770-1775 Jun, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Computing and Processing
Signal Processing and Analysis
Buildings
Cryptography
Information theory
- Language
- ISSN
- 2157-8117
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.