Paper 2023/1088 Original: eprint.iacr.org/2023/1088 ↗
Building Hard Problems by Combining Easy Ones
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2023-11-01: last updated
- 2023-07-13: published
- Short URL
- https://ia.cr/2023/1088
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/1088,
author = {Riddhi Ghosal and Amit Sahai},
title = {Building Hard Problems by Combining Easy Ones},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1088},
year = {2023},
url = {https://eprint.iacr.org/2023/1088}
}